Verified answer

Resposta: O menor natural n que satisfaz as condições do enunciado é 71 (setenta e um).

Explicação passo a passo:

Queremos encontrar o menor natural n, de modo que a equação

    nᵏ ≡ 111 ... 111   (mod 10²⁰¹²)       (i)

        ⁽²⁰¹² ᵃˡᵍᵃʳᶦˢᵐᵒˢ⁾

possui solução para algum k natural. Como mdc(9, 10²⁰¹²) = 1, podemos multiplicar ambos os lados por 9, e obtemos uma congruência equivalente:

    ⟺   9nᵏ ≡ 999 ... 999   (mod 10²⁰¹²)

                   ⁽²⁰¹² ᵃˡᵍᵃʳᶦˢᵐᵒˢ⁾

    ⟺   9nᵏ ≡ − 1  (mod 10²⁰¹²)

    ⟺   9nᵏ ≡ − 1  (mod 2²⁰¹²)       (ii)

          9nᵏ ≡ − 1  (mod 5²⁰¹²)       (iii)

• Análise módulo 2:

    9nᵏ ≡ − 1  (mod 2)

    ⟺   nᵏ ≡ 1  (mod 2)

    ⟺   n ≡ 1  (mod 2)       (iv)

Logo, n é ímpar.

• Análise módulo 4:

    9nᵏ ≡ − 1  (mod 4)

    ⟺   nᵏ ≡ 3  (mod 4)       (v)

Como n é ímpar, por (iv), devemos ter

    ⟹   n ≡ 1  (mod 4)   ou   n ≡ 3  (mod 4)

Descartamos a possibilidade de n ≡ 1 (mod 4), pois contradiz (v). Logo, devemos ter

    ⟹   n ≡ 3  (mod 4)       (vi)

Além disso, por (v) e (vi), podemos concluir também que k é ímpar.

• Análise módulo 8:

    9nᵏ ≡ − 1  (mod 8)

    ⟺   nᵏ ≡ 7  (mod 8)       (vii)

Por outro lado, por (vi), temos

    ⟹   n ≡ 3  (mod 8)   ou   n ≡ 7  (mod 8)

Descartamos a possibilidade de n ≡ 3 (mod 8), pois contradiz (vii). Logo, devemos ter

    ⟺   n ≡ 7  (mod 8)       (viii)

• Análise módulo 16:

    9nᵏ ≡ − 1  (mod 16)

    ⟺   9 · 9nᵏ ≡ 9 · (− 1)  (mod 16)

    ⟺   81nᵏ ≡ − 9  (mod 16)

    ⟺   nᵏ ≡ 7  (mod 16)       (ix)

Por (viii), devemos ter

    ⟹   n ≡ 7  (mod 16)   ou   n ≡ 15  (mod 16)

    ⟺   n ≡ 7  (mod 16)   ou   n ≡ − 1  (mod 16)

Descartamos a possibilidade de n ≡ − 1 (mod 16), pois contradiz (ix). Logo, devemos ter

    ⟹   n ≡ 7  (mod 16)       (x)

• Análise módulo 5:

    9nᵏ ≡ − 1   (mod 5)

    ⟺   nᵏ ≡ 1   (mod 5)

Como k é ímpar, a única possibilidade é

    ⟹   n ≡ 1  (mod 5)       (xi)

visto que as potências e 2, 3 ou 4 só serão congruentes a 1 se o expoente for par.

Por (x) e (xi), montamos um sistema linear de congruências:

    n ≡ 7  (mod 16)       (x)

    n ≡ 1  (mod 5)        (xi)

Resolvendo o sistema. Por (x), segue que

    ⟹   n = 16a + 7       (xii)

Substituindo em (xi), temos

    ⟹   16a + 7 ≡ 1  (mod 5)

    ⟺   16a ≡ − 6 ≡ 4  (mod 5)

    ⟺   a ≡ 4  (mod 5)

    ⟺   a ≡ 5b + 4       (xiii)

Substituindo em (xii), encontramos

    ⟹   n = 16(5b + 4) + 7

    ⟺   n = 80b + 64 + 7

    ⟺   n = 80b + 71

    ⟺   n ≡ 71 (mod 80)       (xiv)

Verifiquemos que n = 71 é de fato a menor solução para o problema:

    71ᵏ ≡ 111 ... 111   (mod 10²⁰¹²)         ⁽²⁰¹² ᵃˡᵍᵃʳᶦˢᵐᵒˢ⁾

    ⟺   71ᵏ ≡  (10²⁰¹² − 1)/9   (mod 10²⁰¹²)

    ⟺   71ᵏ ≡  (10²⁰¹² − 1)/9   (mod 2²⁰¹²)            (xv)

            71ᵏ ≡  (10²⁰¹² − 1)/9   (mod 5²⁰¹²)            (xvi)

Calculando as ordens de 71 módulo 2²⁰¹² e 5²⁰¹², encontramos

    [tex]\mathrm{ord}_{(2^{2012})}(71)=2^{2012-3}=2^{2009}\\\\ \mathrm{ord}_{(5^{2012})}(71)=5^{2012-1}=5^{2011}[/tex]

(os cálculos das ordens estão disponíveis na tarefa do link a seguir: https://brainly.com.br/tarefa/55168466)

Então, as potências de 71 deixam 2²⁰⁰⁹ restos distintos na divisão por 2²⁰¹². É possível que (10²⁰¹² − 1)/9 seja congruente a um desses restos, módulo 2²⁰¹²? Vejamos:

Analisando módulo 16, temos:

    71ʰ ≡ r   (mod 16)            (xvii)

    ⟺   7ʰ ≡  r   (mod 16)

    ⟺   r ≡ 1   (mod 16)   ou   r ≡ 7   (mod 16)

    ⟺   r = 16a + 1   ou   r = 16a + 7

Contando quantos restos existem na divisão por 2²⁰¹² na forma 16a + 1 ou 16a + 7:

    ⟹   r ∈ {1, 17, 33, ... , 2²⁰¹² − 15} ∪ {7, 23, 39, ... , 2²⁰¹² − 9}

Os elementos dos conjuntos formam uma P.A. de razão 16. Sendo m a quantidade de termos do primeiro conjunto, temos

    aₘ = a₁ + (m − 1) · 16

    ⟺   16(2²⁰⁰⁸) − 15 = 1 + (m − 1) · 16

    ⟺   16(m − 1) = 16(2²⁰⁰⁸) − 15 − 1

    ⟺   16(m − 1) = 16(2²⁰⁰⁸) − 16

    ⟺   16(m − 1) = 16 · (2²⁰⁰⁸ − 1)

    ⟺   m − 1 = 2²⁰⁰⁸ − 1

    ⟺   m = 2²⁰⁰⁸

Logo, existem 2²⁰⁰⁸ restos na forma 16a + 1, e de forma análoga, concluímos que também existem 2²⁰⁰⁸ restos na forma 16a + 7.

Então, existem

    2²⁰⁰⁸ + 2²⁰⁰⁸ = 2 · 2²⁰⁰⁸ = 2²⁰⁰⁹

restos possíveis que satisfazem a congruência (xvii). Como [tex]2^{2009}=\mathrm{ord}_{(2^{2012})}(71),[/tex] e

    (10²⁰¹² − 1)/9 ≡ 1111 ≡ 7  (mod 16)

garantimos que (10²⁰¹² − 1)/9 é congruente a um desses restos para alguma potência de 71, ou seja, existe h inteiro positivo, tal que

    71ʰ ≡  (10²⁰¹² − 1)/9   (mod 2²⁰¹²)

De forma análoga, analisando módulo 5, concluímos que existem 5²⁰¹¹ restos possíveis na divisão por 5²⁰¹² na forma 5a + 1, os que possuem o algarismo das unidades igual a 1 ou igual a 6.

Como [tex]5^{2011}=\mathrm{ord}_{(5^{2012})}(71),[/tex] e o algarismo das unidades de (10²⁰¹² − 1)/9 é 1

    (10²⁰¹² − 1)/9 ≡ 1  (mod 5)

então garantimos que (10²⁰¹² − 1)/9 é congruente a um desses restos para alguma potência de 71, ou seja, existe j inteiro positivo, tal que

    71ʲ ≡  (10²⁰¹² − 1)/9   (mod 5²⁰¹²)

Dados tais h, j, é suficiente mostrar que existe k inteiro positivo, tal que

    71ᵏ ≡ 71ʰ   (mod 2²⁰¹²)

    71ᵏ ≡ 71ʲ   (mod 5²⁰¹²)

No entanto,

    aˣ ≡ aʸ   (mod m)  ⟺   x ≡ y   (mod ordₘ(a))

Logo, como [tex]\mathrm{ord}_{(2^{2012})}(71)=2^{2009}[/tex] e [tex]\mathrm{ord}_{(5^{2012})}(71)=5^{2011}[/tex], basta mostrarmos o sistema

    k ≡ h   (mod 2²⁰⁰⁹)

    k ≡ j   (mod 5²⁰¹¹)

possui solução. Pelo Teorema Chinês dos Restos, garantimos que o sistema acima possui solução para k pois mdc(2²⁰⁰⁹, 5²⁰¹¹) = 1. Portanto, existe k natural, tal que

    71ᵏ ≡  (10²⁰¹² − 1)/9   (mod 10²⁰¹²)               ■

Salba mais sobre congruência modular e ordem:

https://brainly.com.br/tarefa/55168466

https://brainly.com.br/tarefa/55131156

https://brainly.com.br/tarefa/55099729

https://brainly.com.br/tarefa/55120767