Olimpíadas ⇒ JBMO 2022 Equação diofantina Tópico resolvido
-
Babi123
- Mensagens: 1374
- Registrado em: 28 Jul 2017, 21:05
- Última visita: 02-06-24
- Agradeceu: 1195 vezes
- Agradeceram: 271 vezes
Jul 2022
02
19:43
JBMO 2022 Equação diofantina
Determine todas as quádruplas de inteiros positivos [tex3](p,q,a,b)[/tex3]
, onde [tex3]p[/tex3]
e [tex3]q[/tex3]
são números primos e [tex3]a>1[/tex3]
, de tal modo que: [tex3]p^a=1+5q^b[/tex3]
.
Editado pela última vez por Babi123 em 02 Jul 2022, 19:45, em um total de 1 vez.
Jul 2022
03
18:42
Re: JBMO 2022 Equação diofantina
rascunho e incompleto!!!!!! vou deixar aqui caso alguém queira terminar, eu travei ali e tbm eu n revisei e isso deve estar muito mal escrito já q fui escrevendo conforme fui tentar diferentes ideias
depois eu volto a tentar se ngm terminar
[tex3]p^a - 1 = 5q^b[/tex3] mas se lembrarmos da fatoração [tex3]x^n - y^n = (x-y)(x^{n-1} + x^{n-2}y + ... + y^{n-2}x + y^n)[/tex3] descobrimos que
[tex3]p-1|5q^b[/tex3] se p for maior q 2, p é ímpar então p -1 é par
ou seja, se p > 2 a gente só pode ter q = 2.
primeiro caso: p = 2:
[tex3]2^a -1= 5q^b[/tex3] olhando mod 5 temos:
[tex3]2^a \equiv 1 \pmod{5}\implies 4 = ord_52|a[/tex3] , a = 4c
[tex3]8^c-1= 5q^b[/tex3] mas ai 7 divide o lado esquerdo pela fatoração e a gente descobre q q = 7
[tex3]8^c - 1 = 5\cdot7^b[/tex3]
[tex3]8| (-1)^b\cdot5 + 1[/tex3] q n é falso n importando a paridade de b
segundo caso: p > 2.
[tex3]p^a - 1 = 2^b\cdot 5[/tex3]
(aqui tá errado)
[tex3]p-1|2^b\cdot 5[/tex3] se p não for potencia de 2 + 1 a gente tem que p - 1|5 q nos deixa com p - 1 = 1 ou p - 1 = 5, nos 2 casos a gente n tem sol já que (p não é potencia de 2 mais 1 e p > 2)
pelo outro caso.
[tex3]p = 2^c + 1[/tex3]
[tex3](2^c+1)^a - 1 = 2^b\cdot 5[/tex3]
[tex3][/tex3]
[tex3]p^{mdc(a, 4) } \equiv 1\pmod 5[/tex3]
claramente a ímpar n funciona então vamos ver a par. por lte a gente tem que
subcaso 1:
[tex3]p^2\equiv 1 \pmod 5\\
(p-1)(p+1)\equiv0\pmod 5\\
2^c + 2 \equiv 0\pmod 5\implies
2^{c-1} + 1\equiv 0\pmod 5[/tex3] isso implica c-1 par pq 2(c-1) é divisível por 4 (ordem de 2 mod 5)
dai [tex3]2^c + 1 = 2\cdot4^{\frac{c-1}{2}} + 1[/tex3] e isso é divisível por 3
dai c = 1 e fica
[tex3]3^a - 1 = 2^b\cdot 5[/tex3]
(voltar dps)
subcaso 2:
[tex3]4|a\rightarrow a = 4k[/tex3]
podemos assumir c par se n a gente cai no caso anterior
[tex3](2^c+1)^{4k} - 1= 2^b\cdot 5[/tex3]
[tex3]((-1)^c + 1)^{4k} - 1 = (-1)^{b+1}\pmod 3[/tex3]
os resíduos quadráticos mod 3 são 1 ou 0 ai a úncia possibilidade é aquilo 1 - 1 = 0 = (-1)^{b+1} ou 0 - 1 = (-1)^{b+1} dai claramente a primeira opção n é, dai ((-1)^c + 1)^{4k} é 0 mas para isso o de dentro precisa ser 0 mas c é par, absurdo
voltando
depois eu volto a tentar se ngm terminar
Resposta
[tex3]p^a - 1 = 5q^b[/tex3] mas se lembrarmos da fatoração [tex3]x^n - y^n = (x-y)(x^{n-1} + x^{n-2}y + ... + y^{n-2}x + y^n)[/tex3] descobrimos que
[tex3]p-1|5q^b[/tex3] se p for maior q 2, p é ímpar então p -1 é par
ou seja, se p > 2 a gente só pode ter q = 2.
primeiro caso: p = 2:
[tex3]2^a -1= 5q^b[/tex3] olhando mod 5 temos:
[tex3]2^a \equiv 1 \pmod{5}\implies 4 = ord_52|a[/tex3] , a = 4c
[tex3]8^c-1= 5q^b[/tex3] mas ai 7 divide o lado esquerdo pela fatoração e a gente descobre q q = 7
[tex3]8^c - 1 = 5\cdot7^b[/tex3]
[tex3]8| (-1)^b\cdot5 + 1[/tex3] q n é falso n importando a paridade de b
segundo caso: p > 2.
[tex3]p^a - 1 = 2^b\cdot 5[/tex3]
(aqui tá errado)
[tex3]p-1|2^b\cdot 5[/tex3] se p não for potencia de 2 + 1 a gente tem que p - 1|5 q nos deixa com p - 1 = 1 ou p - 1 = 5, nos 2 casos a gente n tem sol já que (p não é potencia de 2 mais 1 e p > 2)
pelo outro caso.
[tex3]p = 2^c + 1[/tex3]
[tex3](2^c+1)^a - 1 = 2^b\cdot 5[/tex3]
[tex3][/tex3]
[tex3]p^{mdc(a, 4) } \equiv 1\pmod 5[/tex3]
claramente a ímpar n funciona então vamos ver a par. por lte a gente tem que
subcaso 1:
[tex3]p^2\equiv 1 \pmod 5\\
(p-1)(p+1)\equiv0\pmod 5\\
2^c + 2 \equiv 0\pmod 5\implies
2^{c-1} + 1\equiv 0\pmod 5[/tex3] isso implica c-1 par pq 2(c-1) é divisível por 4 (ordem de 2 mod 5)
dai [tex3]2^c + 1 = 2\cdot4^{\frac{c-1}{2}} + 1[/tex3] e isso é divisível por 3
dai c = 1 e fica
[tex3]3^a - 1 = 2^b\cdot 5[/tex3]
(voltar dps)
subcaso 2:
[tex3]4|a\rightarrow a = 4k[/tex3]
podemos assumir c par se n a gente cai no caso anterior
[tex3](2^c+1)^{4k} - 1= 2^b\cdot 5[/tex3]
[tex3]((-1)^c + 1)^{4k} - 1 = (-1)^{b+1}\pmod 3[/tex3]
os resíduos quadráticos mod 3 são 1 ou 0 ai a úncia possibilidade é aquilo 1 - 1 = 0 = (-1)^{b+1} ou 0 - 1 = (-1)^{b+1} dai claramente a primeira opção n é, dai ((-1)^c + 1)^{4k} é 0 mas para isso o de dentro precisa ser 0 mas c é par, absurdo
voltando
Editado pela última vez por leozitz em 03 Jul 2022, 20:36, em um total de 1 vez.
Razão: avisar erro
Razão: avisar erro
-
FelipeMartin
- Mensagens: 2267
- Registrado em: 04 Jul 2020, 10:47
- Última visita: 10-06-24
- Agradeceu: 29 vezes
- Agradeceram: 27 vezes
Jul 2022
04
07:44
Re: JBMO 2022 Equação diofantina
acho que é bem por esse caminho mesmo:
[tex3](1+5^k \cdot 2^m)^a -1 = 5 \cdot 2^b[/tex3]
Se [tex3]k=0[/tex3] :
[tex3](1+ 2^m)^a -1 = 5 \cdot 2^b[/tex3]
olhemos a expressão esquerda [tex3]\mod 3[/tex3] :
[tex3](1 + (-1)^m)^a -1[/tex3]
com [tex3]m[/tex3] ímpar, temos que a expressão é indivisível por [tex3]3[/tex3] . Não podendo acontecer [tex3]m[/tex3] par e [tex3]a[/tex3] par também.
[tex3]p-1 | 2^b \cdot 5[/tex3] , então: [tex3]p-1 = 5^k \cdot 2^m[/tex3] com [tex3]0 \leq m \leq b[/tex3] e [tex3]k \in \{0,1\}[/tex3] .leozitz escreveu: ↑03 Jul 2022, 18:42
[tex3]p^a - 1 = 5q^b[/tex3] mas se lembrarmos da fatoração [tex3]x^n - y^n = (x-y)(x^{n-1} + x^{n-2}y + ... + y^{n-2}x + y^n)[/tex3] descobrimos que
[tex3]p-1|5q^b[/tex3] se p for maior q 2, p é ímpar então p -1 é par
ou seja, se p > 2 a gente só pode ter q = 2.
primeiro caso: p = 2:
[tex3]2^a -1= 5q^b[/tex3] olhando mod 5 temos:
[tex3]2^a \equiv 1 \pmod{5}\implies 4 = ord_52|a[/tex3] , a = 4c
[tex3]8^c-1= 5q^b[/tex3] mas ai 7 divide o lado esquerdo pela fatoração e a gente descobre q q = 7
[tex3]8^c - 1 = 5\cdot7^b[/tex3]
[tex3]8| (-1)^b\cdot5 + 1[/tex3] q n é falso n importando a paridade de b
segundo caso: p > 2.
[tex3]p^a - 1 = 2^b\cdot 5[/tex3]
[tex3](1+5^k \cdot 2^m)^a -1 = 5 \cdot 2^b[/tex3]
Se [tex3]k=0[/tex3] :
[tex3](1+ 2^m)^a -1 = 5 \cdot 2^b[/tex3]
olhemos a expressão esquerda [tex3]\mod 3[/tex3] :
[tex3](1 + (-1)^m)^a -1[/tex3]
com [tex3]m[/tex3] ímpar, temos que a expressão é indivisível por [tex3]3[/tex3] . Não podendo acontecer [tex3]m[/tex3] par e [tex3]a[/tex3] par também.
φως εσύ και καρδιά μου εγώ πόσο σ' αγαπώ.
Jul 2022
04
16:46
Re: JBMO 2022 Equação diofantina
[tex3]p = 1 + 2^m[/tex3]
[tex3](p)^a -1 = 5 \cdot 2^b[/tex3] mod 5:
[tex3](p)^a \equiv 1 \pmod 5[/tex3]
obs: p claramente n é 5 ai aqui a gente usa o pequeno teorema de fermat
[tex3]p^{mdc(a, 4)}\equiv 1 \pmod{5}[/tex3]
com isso a gente descobre q a é par pq se for ímpar a gente tem mdc = 1 e consegue uma coisa falsa.
a = 2k
[tex3](1 + 2^m)^{2k}-1 = 2^b\cdot 5[/tex3]
[tex3]((1+2^m)^k + 1)((1 + 2^m)^k - 1) = 2^b\cdot 5[/tex3]
se p n for divisível por 3 então um dos dois fatores do lado esquerdo vai ser, enquanto o lado direito n é, um absurdo então p = 3.
[tex3]3^a - 1 = 2^b\cdot 5[/tex3]
usando lte
[tex3]v_2(3^a - 1) = v_2(4) + v_2(2) + v_2(a) - 1 = 2 + v_2(a) = b[/tex3]
agora algo me diz q o lado esquerdo fica muito grande
usando a melhor estimativa possível: v_2(a) <= a - 2 para a > 2 acho q deve dar para provar isso com indução
[tex3]b\le a[/tex3]
[tex3]5\cdot 2^b = 3^a -1 \ge 3^b - 1 [/tex3]
e isso deve ficar falso rápido ai a gente testa esses casos.
[tex3](p)^a -1 = 5 \cdot 2^b[/tex3] mod 5:
[tex3](p)^a \equiv 1 \pmod 5[/tex3]
obs: p claramente n é 5 ai aqui a gente usa o pequeno teorema de fermat
[tex3]p^{mdc(a, 4)}\equiv 1 \pmod{5}[/tex3]
com isso a gente descobre q a é par pq se for ímpar a gente tem mdc = 1 e consegue uma coisa falsa.
a = 2k
[tex3](1 + 2^m)^{2k}-1 = 2^b\cdot 5[/tex3]
[tex3]((1+2^m)^k + 1)((1 + 2^m)^k - 1) = 2^b\cdot 5[/tex3]
se p n for divisível por 3 então um dos dois fatores do lado esquerdo vai ser, enquanto o lado direito n é, um absurdo então p = 3.
[tex3]3^a - 1 = 2^b\cdot 5[/tex3]
usando lte
[tex3]v_2(3^a - 1) = v_2(4) + v_2(2) + v_2(a) - 1 = 2 + v_2(a) = b[/tex3]
agora algo me diz q o lado esquerdo fica muito grande
usando a melhor estimativa possível: v_2(a) <= a - 2 para a > 2 acho q deve dar para provar isso com indução
[tex3]b\le a[/tex3]
[tex3]5\cdot 2^b = 3^a -1 \ge 3^b - 1 [/tex3]
e isso deve ficar falso rápido ai a gente testa esses casos.
Editado pela última vez por leozitz em 04 Jul 2022, 16:47, em um total de 1 vez.
Jul 2022
04
18:35
Re: JBMO 2022 Equação diofantina
[tex3]p = 1 + 2^m \cdot 5[/tex3]
olhando mod 3 a gente descobre que temos 2 casos
b, m par e ímpar
b e m par e ai a paridade do a n importa mod 3, então vamos começar com a par
nesse caso [tex3]p^a - 1[/tex3] é 0 mod 3, abs
então a é ímpar. mas ai, novamente por lte
[tex3]m + v_2(a) = b\implies m = b[/tex3]
[tex3](1 + 2^b\cdot 5)^a - 1 = 2^b\cdot 5[/tex3] ai a é maior q 1 por hipótese então
[tex3]1 + 2^b\cdot 5 = (1 + 2^b\cdot 5)^a \ge (1 + 2^b\cdot5)^2[/tex3]
[tex3]1 + 2^b\cdot 5 \ge 1 + 2^{b+1}\cdot5 + 2^{2b}\cdot 25[/tex3] q é claramente falso e acho q isso acaba?
b, m par e ímpar
b e m par e ai a paridade do a n importa mod 3, então vamos começar com a par
nesse caso [tex3]p^a - 1[/tex3] é 0 mod 3, abs
então a é ímpar. mas ai, novamente por lte
[tex3]m + v_2(a) = b\implies m = b[/tex3]
[tex3](1 + 2^b\cdot 5)^a - 1 = 2^b\cdot 5[/tex3] ai a é maior q 1 por hipótese então
[tex3]1 + 2^b\cdot 5 = (1 + 2^b\cdot 5)^a \ge (1 + 2^b\cdot5)^2[/tex3]
[tex3]1 + 2^b\cdot 5 \ge 1 + 2^{b+1}\cdot5 + 2^{2b}\cdot 25[/tex3] q é claramente falso e acho q isso acaba?
Jul 2022
04
18:47
Re: JBMO 2022 Equação diofantina
2^4 é 8 sim kkkkk, aqui era pra ser 16, fui olhar em outro site e as soluções q um usuário postou são (p,q,a,b)=(2,3,4,1) e (p,q,a,b)=(3,2,4,4)
ele afirma q essas são as únicas mas n conferi a solução dele e tbm a solução dele parece ser bem mais fácil
-
FelipeMartin
- Mensagens: 2267
- Registrado em: 04 Jul 2020, 10:47
- Última visita: 10-06-24
- Agradeceu: 29 vezes
- Agradeceram: 27 vezes
Jul 2022
04
18:55
Re: JBMO 2022 Equação diofantina
acho que vão aparecer muitos fatores primos no lado esquerdo.
Temos uma solução simples por inspeção: [tex3]a=4, b= 4[/tex3] , então:
[tex3]81-1=80 = 5 \cdot 16[/tex3]
bom, a primeira coisa a notar é que [tex3]3^a[/tex3] tem um padrão bem simples mod [tex3]5[/tex3] :
[tex3]a =0 \implies 3^a \equiv 1 \mod 5[/tex3]
[tex3]a =1 \implies 3^a \equiv -2 \mod 5[/tex3]
[tex3]a =2 \implies 3^a \equiv -1 \mod 5[/tex3]
[tex3]a =3 \implies 3^a \equiv 2 \mod 5[/tex3]
[tex3]a =4 \implies 3^a \equiv 1 \mod 5[/tex3]
pronto, temos um ciclo, pois o mod se multiplica por 3 a cada acréssimo de [tex3]a[/tex3] , então, para [tex3]3^a -1[/tex3] ser divisível por [tex3]5[/tex3] , devemos ter [tex3]a = 4k[/tex3] para [tex3]k \in \{1,2,3,... \}[/tex3] .
[tex3]3^{4k} - 1^{4k} = (3^{2k}-1)(3^{2k}+1) = (3^k-1)(3^k+1)(3^{2k}+1)[/tex3]
repare que o mdc entre [tex3]3^k+1[/tex3] e [tex3]3^k-1[/tex3] é o mesmo mdc entre [tex3]3^k+1[/tex3] e [tex3]2[/tex3] , que deve ser [tex3]2[/tex3] . Portanto, se [tex3]3^k-1[/tex3] tiver fatores primos além de [tex3]2[/tex3] e [tex3]5[/tex3] a coisa já acabou, pois [tex3]3^k+1[/tex3] terá fatores primos novos.
Vejamos como [tex3]3^k-1[/tex3] se comporta:
[tex3]k=1 \implies 3^k-1 =2[/tex3] ([tex3]a=4,b=4[/tex3] )
[tex3]k=2 \implies 3^k-1 = 8[/tex3] , beleza: [tex3]3^k+1 = 10[/tex3] , mas [tex3]3^{2k}+1=82 = 2 \cdot 41[/tex3] .
[tex3]k =3 \implies 3^k-1 = 26 = 13 \cdot 2[/tex3] . Pronto!
A partir daqui, [tex3]3^{k}-1[/tex3] não pode ser uma potência pura de [tex3]2[/tex3] , no máximo, seria [tex3]5 \cdot 2^x[/tex3] , mas isso implicaria que [tex3]3^{k}+1[/tex3] teria um novo fator primo. Portanto, a única solução possível é [tex3]a=4[/tex3] e [tex3]b=4[/tex3] nesse caso.
Editado pela última vez por FelipeMartin em 04 Jul 2022, 18:58, em um total de 1 vez.
φως εσύ και καρδιά μου εγώ πόσο σ' αγαπώ.
-
FelipeMartin
- Mensagens: 2267
- Registrado em: 04 Jul 2020, 10:47
- Última visita: 10-06-24
- Agradeceu: 29 vezes
- Agradeceram: 27 vezes
Jul 2022
04
19:05
Re: JBMO 2022 Equação diofantina
leozitz, ah é verdade, era pra ser [tex3]16^c -1 = 5 q^b[/tex3]
, então tem que mexer um pouco no argumento para [tex3]p=2[/tex3]
. O resto, acho que tá certo.
φως εσύ και καρδιά μου εγώ πόσο σ' αγαπώ.
Jul 2022
04
19:11
Re: JBMO 2022 Equação diofantina
agora q a gente sabe a solução particular fica fácil, mod 3 a gente tem que q = 3.
[tex3]16^c - 1 = 5\cdot3^b[/tex3] agora acredito q dá para usar sua ideia de olhar o mdc para ver que vários fatores primos diferentes.
[tex3](2^c-1)(2^c+1)(4^c+1) = 5\cdot3^b[/tex3]
[tex3]mdc(2^c - 1, 2^c + 1) = mdc(2^c -1, 2) = 1[/tex3]
[tex3]mdc(2^c -1, 4^c + 1) =d[/tex3]
[tex3]d|2^c - 1 \implies d |4^c - 1\implies d | 2[/tex3] mas o nosso numero n é par ai o lado esquerdo tem pelo menos 3 fatores primos diferentes (se c > 1) q é absurdo então c = 1 mas ai fica tranquilo
[tex3]16^c - 1 = 5\cdot3^b[/tex3] agora acredito q dá para usar sua ideia de olhar o mdc para ver que vários fatores primos diferentes.
[tex3](2^c-1)(2^c+1)(4^c+1) = 5\cdot3^b[/tex3]
[tex3]mdc(2^c - 1, 2^c + 1) = mdc(2^c -1, 2) = 1[/tex3]
[tex3]mdc(2^c -1, 4^c + 1) =d[/tex3]
[tex3]d|2^c - 1 \implies d |4^c - 1\implies d | 2[/tex3] mas o nosso numero n é par ai o lado esquerdo tem pelo menos 3 fatores primos diferentes (se c > 1) q é absurdo então c = 1 mas ai fica tranquilo
Jul 2022
04
19:18
Re: JBMO 2022 Equação diofantina
na vdd eu me adiantei um pouco, pode acontecer de 2^c + 1, 4^c + 1 terem os mesmos fatores primos, vamos ver isso
[tex3]mdc(2^c + 1, 4^c + 1) = d[/tex3]
[tex3]d|2^c + 1\implies d|(2^c + 1)(2^c-1) = 4^c - 1[/tex3]
ai d divide 2 e como n tem par d só pode ser 1 então eles n tem fatores primos em comum
[tex3]mdc(2^c + 1, 4^c + 1) = d[/tex3]
[tex3]d|2^c + 1\implies d|(2^c + 1)(2^c-1) = 4^c - 1[/tex3]
ai d divide 2 e como n tem par d só pode ser 1 então eles n tem fatores primos em comum
-
- Tópicos Semelhantes
- Resp.
- Exibições
- Últ. msg
-
- 2 Resp.
- 822 Exibições
-
Últ. msg por RafaeldeLima
-
-
Nova mensagem (Titu Andreescu-Romênia) Equação Diofantina
por Auto Excluído (ID:17906) » » em Olimpíadas - 0 Resp.
- 984 Exibições
-
Últ. msg por Auto Excluído (ID:17906)
-
-
- 3 Resp.
- 1039 Exibições
-
Últ. msg por Ivo213
-
- 2 Resp.
- 1223 Exibições
-
Últ. msg por Hanon
