[Aritmética: Teoria dos Números – Números naturais – Números primos – Divisibilidade]
Encontre o menor valor natural para n, tal que,
4n(p − 1) + 1 é divisível por p
para todo p ∈ {3, 5, 7}.
Obs: Gentileza não resolver por tentativa e erro (força bruta). Seja claro e detalhado em sua resposta.
Gabarito: 79. [tex]\,[/tex]
Encontre o menor valor natural para n, tal que,
4n(p − 1) + 1 é divisível por p
para todo p ∈ {3, 5, 7}.
Obs: Gentileza não resolver por tentativa e erro (força bruta). Seja claro e detalhado em sua resposta.
Gabarito: 79. [tex]\,[/tex]
More Questions From This User See All
Lista de comentários
Verified answer
Resposta: n corresponderá a todos os números da forma [tex]n=105q+79\:|\:q\in \mathbb{N}[/tex]. Quando q = 0, vemos que o menor valor natural assumido por n é, de fato, igual a 79. Vamos ver por quê.
Construindo a expressão
Uma boa forma de se aproximar dessa questão é partir de uma congruência fundamental e ir acrescentando, passo a passo, termos que a façam incidir na expressão final.
Sabemos que todo número natural é divisível por ele mesmo, então comecemos daí:
[tex]p\equiv 0\:(mod\:p)[/tex]
Subtraindo 1 dos dois lados da congruência:
[tex]p-1\equiv -1\:(mod\:p)[/tex]
Multiplicando por 4n:
[tex]4n(p-1)\equiv -4n\:(mod\:p)[/tex]
Finalmente, somamos 1:
[tex]4n(p-1)+1\equiv -4n+1\:(mod\:p)\:\:\:\:\:\:(i)[/tex]
Chegamos à expressão final, cuja divisibilidade por p desejamos avaliar. Queremos:
[tex]4n(p-1)+1\equiv0\:(mod\:p)\:\:\:\:\:\:(ii)[/tex]
Pela transitividade das congruências [tex](i)[/tex] e [tex](ii)[/tex], podemos afirmar:
[tex]-4n+1\equiv0 \:(mod\:p)[/tex]
[tex]4n\equiv1 \:(mod\:p)\:\:\:\:\:\:(iii)[/tex]
Análise
Sabendo que p ∈ {3, 5, 7}, abriremos [tex](iii)[/tex] em três congruências distintas, as quais comporão um sistema.
[tex]4n\equiv 1\:(mod\:3)\\4n\equiv 1\:(mod\:5)\\4n\equiv 1\:(mod\:7)[/tex]
Sabendo que MMC(3,5,7) = 105, fazemos:
[tex]35.4n\equiv 35.1\:(mod\:35.3)\\21.4n\equiv 21.1\:(mod\:21.5)\\15.4n\equiv 15.1\:(mod\:15.7)[/tex]
Resultando:
[tex]140n\equiv 35\:(mod\:105) \Longrightarrow (105+35)n\equiv 35\:(mod\:105) \Longrightarrow 35n\equiv 35\:(mod\:105)\\84n\equiv 21\:(mod\:105)\\60n\equiv 15\:(mod\:105)[/tex]
Percebemos que 35 + 84 + 60 = 179, e que MDC(179,105) = 1, o que indica que existem representantes da classe inversa de 179 módulo 105. Esse fato garante que podemos fazer, convenientemente:
[tex](-1).35n\equiv (-1)35\:(mod\:105)\\(-1).84n\equiv (-1).21\:(mod\:105)\\2.60n\equiv 2.15\:(mod\:105)[/tex]
Conclusão
Realizando os produtos e somando as congruências resultantes, teremos:
[tex]120n-84n-35n\equiv30-35-21\:(mod\:105)[/tex]
[tex]n\equiv -26\:(mod\:105)[/tex]
[tex]n\equiv 79-105\:(mod\:105)[/tex]
[tex]n\equiv 79\:(mod\:105)[/tex]
Com isso, concluímos que n será da forma n = 105q + 79, com q natural, e que 79 é o menor valor natural possível.