Ensino Médio

É possível concluir que [tex3]3^{1024}-1 \equiv 0 \ (mod\ 2^{12})[/tex3] a partir de [tex3]3^{1024}-1 \equiv 0 \ (mod\ 2^{11})[/tex3] ?

Digo isso porque a questão pede a maior potência de 2 que divide [tex3]3^{1024}-1[/tex3] , e eu não gostei da resolução dada, então tentei por outro jeito. No caso fui pelo teorema de Euler. [tex3]\phi(2^n)=2^{n-1}[/tex3] , então teríamos logo de cara que [tex3]3^{1024}-1 \equiv 0 \ (mod \ 2^{11})[/tex3] , mas essa ainda não é a maior potência de 2 que divide a tal expressão.

Mensagem não lidapor **jedi** » Dom 12 Fev, 2017 11:13 · Mensagem não lida por **jedi** » Dom 12 Fev, 2017 11:13

pensei no seguinte

[tex3]3^{1024}-1=(3^{512}+1)(3^{512}-1)[/tex3]

[tex3]3^{1024}-1=(3^{512}+1)(3^{256}+1)(3^256-1)[/tex3]

[tex3]3^{1024}-1=(3^{512}+1)(3^{256}+1)(3^{128}+1)(3^{128}-1)[/tex3]

assim sucessivamente

[tex3]3^{1024}-1=(3^{512}+1)(3^{256}+1)(3^{128}+1)(3^{64}+1)\dots(3^{2}+1)(3+1)(3-1)[/tex3]

como três elevado a qualquer numero é igual à um numero ímpar, somado com 1 sempre será par, portanto todos os termos entre parênteses são par e portanto divisíveis por dois.

como temos 11 termos, então já sabemos que é divisível por [tex3]2^{11}[/tex3]

mas o termo 3+1=4 é divisível por 2 duas vezes então concluímos que o número é divisível por [tex3]2^{12}[/tex3]

A solução está certa mas não está rigorosa. Você precisaria provar que esses termos pares só são divisíveis por 2 e não por uma potência maior, se não você não sabe realmente quantas potências de 2 cada termo apresenta. Provando isso, sua solução fica igual a que eu tenho aqui, mas queria ver se tem como dar o pulo do [tex3]2^{11}[/tex3] para [tex3]2^{12}[/tex3] apenas por artifícios de teoria dos números digamos, sem ter que fatorar a expressão inteira e tudo mais.

Mensagem não lidapor **jedi** » Dom 12 Fev, 2017 14:28 · Mensagem não lida por **jedi** » Dom 12 Fev, 2017 14:28

Não consegui encontrar uma forma de a partir da primeira afirmação chegar a segunda, mas acredito que mesmo que conseguisse, você cairia no mesmo problema, conseguiria prova que [tex3]3^{1024}-1[/tex3] é divisivel por [tex3]2^{12}[/tex3] mas teria que encontrar alguma forma de provar que esta é a maior potência de 2 pela qual a expressão é divisivel.

com relação a demonstração de cada termo ser divisivel por 2 apenas uma vez

[tex3]3^n+1=(2+1)^2+1[/tex3]

[tex3]=2^n+n.2^{n-1}+\begin{pmatrix}n\\2\end{pmatrix}2^{n-2}+\begin{pmatrix}n\\3\end{pmatrix}2^{n-3}+\dots+\begin{pmatrix}n\\2\end{pmatrix}2^{2}+n.2+1+1[/tex3]

dividindo por 2

[tex3]=2^{n-1}+n.2^{n-2}+\begin{pmatrix}n\\2\end{pmatrix}2^{n-3}+\begin{pmatrix}n\\3\end{pmatrix}2^{n-3}+\dots+\begin{pmatrix}n\\2\end{pmatrix}2+n+1[/tex3]

se dividirmos uma segunda vez por 2

[tex3]=2^{n-2}+n.2^{n-3}+\begin{pmatrix}n\\2\end{pmatrix}2^{n-4}+\begin{pmatrix}n\\3\end{pmatrix}2^{n-5}+\dots+\begin{pmatrix}n\\2\end{pmatrix}+\frac{n+1}{2}[/tex3]

portanto para que seja divisivel por 2 mais de uma vez, n+1 tem que ser divisivel por 2. Na expressão fatorada isso é verdade apenas quando n=1 nos demais casos n+1 é sempre ímpar portanto todos os demais termos são divisíveis por 2 apenas 1 vez

Estava fuçando aqui nos meus materiais de olimpíadas e como pude esquecer do Lifting the Exponent Lemma...

Copiando direto do arquivo que tenho:
"Let p be a prime number and let x and y be two (not necessary positive) integers that are not divisible by p. Then:
a) For a positive integer n
• if [tex3]p \neq 2[/tex3] and [tex3]p | x − y[/tex3] , then
[tex3]v_p(x^n − y^n) = v_p(x − y) + v_p(n)[/tex3] .
• if [tex3]p = 2[/tex3] and [tex3]4 | x − y[/tex3] , then
[tex3]v_2(x^n − y^n) = v_2(x − y) + v_2(n)[/tex3] .
• if [tex3]p = 2[/tex3] , n is even, and [tex3]2 | x − y[/tex3] , then
[tex3]v_2(x^n − y^n) = v_2(x − y) + v_2(x + y) + v_2(n) − 1[/tex3] .
b) For an odd positive integer n, if [tex3]p | x + y[/tex3] , then
[tex3]v_p(x^n + y^n) = v_p(x + y) + v_p(n)[/tex3] .
c) For a positive integer n with [tex3]gcd(p, n) = 1[/tex3] , if [tex3]p | x − y[/tex3] , we have
[tex3]v_p(x^n − y^n) = v_p(x − y)[/tex3] .
If n is odd, [tex3]gcd(p, n) = 1[/tex3] , and [tex3]p | x + y[/tex3] , then we have
[tex3]v_p(x^n + y^n) = v_p(x + y)[/tex3] ."

Sendo [tex3]v_p(x^n\pm y^n)[/tex3] a maior potência de p que divide [tex3]x^n \pm y^n[/tex3] .

Para o caso da questão, temos [tex3]3^{2^{10}}-1^{2^{10}}[/tex3] , com [tex3]p=2[/tex3] . Note que estamos no terceiro caso da letra a), p=2, [tex3]2^{10}[/tex3] é par e [tex3]2|(3-1)|[/tex3] , então:
[tex3]v_2(3^{2^{10}}-1)=v_2(3-1)+v_2(3+1)+v_2(2^{10})-1=1+2+10-1=12[/tex3]

Ensino Médio ⇒ Congruência Tópico resolvido

Congruência

Re: Congruência

Re: Congruência

Re: Congruência

Re: Congruência

Ensino Médio ⇒ Congruência Tópico resolvido

Congruência

Re: Congruência

Re: Congruência

Re: Congruência

Re: Congruência

Entrar • Registrar