¿Cuál es el mayor $n$ $4^n$ que divide $7^{2048} - 1$?

Question

Hace un par de días me topé con la siguiente pregunta, que fue utilizado en el Museo de las matemáticas torneo de maestros:

¿Cuál es el mayor número entero $n$$4^n$, que se divide $7^{2048} - 1$?

a) 1

b) 3

c) 5

d) 7

No fue formulada exactamente así, pero es lo suficientemente similar.

Usando el intérprete y un terminal de python he adivinado la respuesta es 7. Pero no sé cómo hacerlo usando sólo lápiz y papel.

Answer 1

Deje $\, \upsilon_p(n)\, $ denotar $\, m\, $ s.t. $\, p^m\mid n\, $ $\, p^{m+1}\nmid n$.

LTE (Levantar El Exponente Lema):

$a,b$ impar, $n$ incluso$\ \Rightarrow\,\, \upsilon_2(a^n-b^n)=\upsilon_2(a-b)+\upsilon_2(a+b)+\upsilon_2(n)-1$

$7,1$ son impares, $2048$ es par, entonces

$\upsilon_2(7^{2048}-1^{2048})=\upsilon_2(7-1)+\upsilon_2(7+1)+\upsilon_2(2048)-1=1+3+11-1=2\cdot \textbf{7}$

Answer 2

Lema: si $4\mid n-1$,luego $$||n^k-1||_4=||n-1||_4+||k||_4$$($a=||n||_b$ is the bigger power of b such that $b^a\a mediados de n$) este es un famoso lema cuya prueba es por inducción sobre $k$ 4/7^2-1 así que tenemos $||(7^2)^{1024}||=5+2=7$$

Answer 3

Bien, usted está buscando para encontrar el mayor $n$ tal que $7^{2048}\equiv1$ (mod $4^n$) y, desde $7$ $4^n$ son coprime usted sabe $7^{\varphi(4^n)}\equiv1$ (mod $4^n$) desde el teorema de Euler. Y $\varphi(4^n)=\varphi(2^{2n})=2^{2n-1}(2-1)=2^{2n-1}$.

Ahora, $2048=2^{11}=2^{2\times6-1}=\varphi(4^6)$. Por lo $n=6$ es un límite inferior.

Lamentablemente, creo que es la parte fácil. Usted necesitará otro enfoque para probar si $n=7$ también funciona.

Answer 4

Como $2048=2^{11},$

$$(8-1)^{2048}-1=-1+(1-8)^{2048}$$

$$=-1+1-2048\cdot8+\binom{2048}28^2-\binom{2048}38^3+\cdots$$

$$=-2^{11}2^3+2^{10}\cdot2047\cdot2^6-2^92^{11}\cdot2047\cdot341+\cdots\text{ as }2046=6\cdot341$$

$$=2^{14}[-1+2^2\cdot2047-2^6\cdot2047\cdot341+\text{ higher powers of }2]$$

Claramente, $-1+2^2\cdot2047-2^6\cdot2047\cdot341+\text{ higher powers of }2$ es impar