Álgebra

Outros

23. Provar ou dar um contra exemplo: “Se a e m são inteiros, mdc(a, m) = 1, então m | (1 + a + a2 + ... + a(m)  1).

Desafios para Aprender

ano passado

Desafios para Aprender

ano passado

Resolução Teoria dos Numeros Plinio Cap 2

Resolução Teoria dos Numeros Plinio Cap 2

UNI-FACEF

Respostas

Ed

ano passado

Para provar a afirmação dada, podemos considerar o Teorema de Euler-Fermat, que afirma que se \(a\) e \(m\) são inteiros positivos primos entre si, então \(a^{\phi(m)} \equiv 1 \pmod{m}\), onde \(\phi(m)\) é a função totiente de Euler, que representa a quantidade de inteiros positivos menores que \(m\) e primos entre si a \(m\). Assim, se \(mdc(a, m) = 1\), temos que \(a\) e \(m\) são primos entre si. Portanto, podemos aplicar o Teorema de Euler-Fermat para concluir que \(a^{\phi(m)} \equiv 1 \pmod{m}\). Dessa forma, podemos afirmar que \(m | (1 + a + a^2 + ... + a^{\phi(m)-1})\), o que confirma a afirmação dada.

Essa resposta te ajudou?

0

0

left-side-bubbles-background

right-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Resolução Teoria dos Numeros Plinio Cap 2

Resolução Teoria dos Numeros Plinio Cap 2

UNI-FACEF

Mais perguntas desse material

1. Mostrar que 47 | 223  1. Para mostrar que 47 | 223  1, devemos mostrar que 223 ≡ 1 (mod 47). Notemos que 210 = 1024 = 37 + 47  21. Ou seja, 210 ≡ 37 (mod 47) ⇒ 210 ≡ 10 (mod 47). Então, [210]2 ≡ (10)2 (mod 47) ⇒ 220 ≡ 100 (mod 47) ⇒ 220 ≡ 6 (mod 47) (I) Vejamos, agora, que 23 = 8 = 47  39, ou seja, 23 ≡ 39 (mod 47) (II). De (I) e (II), (220  23) ≡ 6  (39) (mod 47) ⇒ 223 ≡ 234 (mod 47). Mas, 234 = 1  47  5, então 223 ≡ 1 (mod 47).

2. Encontrar o resto da divisão de 734 por 51 e o resto da divisão de 563 por 29. i) Vejamos que 72 ≡ 2 (mod 51). Então, (72)17 ≡ (2)17 (mod 51) ⇒ 734 ≡ 217 (mod 51). (I) Porém, ≡ ≡ } ⇒ 210  27 ≡ 4  26 (mod 51) ⇒ 217 ≡ 104 (mod 51) ⇒ 217 ≡ 2 (mod 51). Dessa forma, 217 ≡ 2 (mod 51) ⇒ 217 ≡ 49 (mod 51). (II) De (I) e (II), temos que 734 ≡ 49 (mod 51), o que indica que o resto da divisão de 734 por 51 é 49. ii) Notemos que 53 ≡ 9 (mod 29), o que nos dá: 563 ≡ 921 (mod 29). Como 9 = 32, 563 ≡ 342 (mod 29) (I) Mas, 33 ≡ 2 (mod 29) ⇒ 342 ≡ (2)16 (mod 29) ⇒ 342 ≡ 216 (mod 29) (II) No entanto, 28 ≡ 13 (mod 29) ⇒ (28)2 ≡ 132 (mod 29) ⇒ 216 ≡ 169 (mod 29) ⇒ 216 ≡ 24 (mod 29) (III). De (I), (II) e (III), temos que 563 ≡ 24 (mod 29), ou seja, o resto da divisão de 563 por 29 é 24.

4. Provar que para p primo (p  1)! ≡ p  1 (mod 1 + 2 + ... + (p  1)). Notemos que: (p  1) ≡  1 (mod p) e (p  1)! ≡ 1 (mod p) (Teorema de Wilson). Pela transitividade, teremos que: (p  1)! ≡ p  1 (mod p). Isso nos mostra que p | (p  1)!  (p  1). Temos, também, que (p  1)!  (p  1) = (p  1)  [(p  2)!  1], ou seja, p  1 | (p  1)!  (p  1). Disso, segue que p  1 | (p  1)!  (p  1). Como p e p  1 são primos entre si, temos que p  p  1 | (p  1)!  (p  1), ou seja, (p  1)! ≡ p  1 ( p  p  1). Notando, porém, que 1 + 2 + ... + (p  1) = p  p  1, tem-se provado o resultado.

10. Seja f(x) = a0 + a1x + ... + anxn um polinômio com coeficientes inteiros onde an > 0 e n  1. Mostrar que f(x) é composto para infinitos valores da variável x.

11. Mostrar que se p1 e p2 são primos tais que p2 = p1 + 2 e p1 > 3, então p1 + p2 ≡ 0 (mod 12). Vejamos que, dividindo um número por, obtemos números da forma 6k, 6k + 1, 6k + 2, 6k + 3, 6k + 4 e 6k + 5. Notemos, também, que 6k, 6k + 2, 6k + 3 e 6k + 4 não são primos. Dessa forma, os números primos são da forma 6k + 1 ou 6k + 5. Como p1 > 3, então p1  5, ou seja, p2  7. Então: Se p1 = 6k + 5, então p2 = 6k + 7, ou seja, p1 + p2 = 12k + 12 = 12(k + 1). Então, p1 + p2 ≡ 0 (mod 12). Se p2 = 6k + 1, então p1 = 6k  1, ou seja, p1 + p2 = 12k. Então, p1 + p2 ≡ 0 (mod 12). ∎ Observação: Notemos que: Se p1 = 6k + 1, então p2 = 6k + 3 (Absurdo, pois p2 é primo). Se p2 = 6k + 5, então p1 = 6k + 3 (Absurdo, pois p1 é primo).

12. Mostrar que para a e b inteiros temos que 3 | (a2 + b2) ⇒ 3 | a e 3 | b. Suponhamos que 3 não divida a pelo menos um entre a e b (suponhamos que 3  a, sem perda de generalidade). Teremos, assim, 6 casos para analisar: (I) a ≡ 1 (mod 3) e b ≡ 0 (mod 3). Dessa forma, { a ≡ 3 b ≡ 3 ⇒ a 2 + b 2 ≡ 0 (mod 3) ⇒ 3  a 2 + b 2 (Absurdo!). (II) a ≡ 1 (mod 3) e b ≡ 1 (mod 3). Dessa forma, { a ≡ 3 b ≡ 3 ⇒ a 2 + b 2 ≡ 2 (mod 3) ⇒ 3  a 2 + b 2 (Absurdo!). (III) a ≡ 1 (mod 3) e b ≡ 2 (mod 3). Dessa forma, { a ≡ 3 b ≡ 3 ≡ 3 ⇒ a 2 + b 2 ≡ 2 (mod 3) ⇒ 3  a 2 + b 2 (Absurdo!). (IV) a ≡ 2 (mod 3) e b ≡ 0 (mod 3). Dessa forma, { a ≡ 3 ≡ 3 b ≡ 3 ⇒ a 2 + b 2 ≡ 1 (mod 3) ⇒ 3  a 2 + b 2 (Absurdo!). (V) a ≡ 2 (mod 3) e b ≡ 1 (mod 3). Dessa forma, { a ≡ 3 ≡ 3 b ≡ 3 ⇒ a 2 + b 2 ≡ 2 (mod 3) ⇒ 3  a 2 + b 2 (Absurdo!). (VI) a ≡ 2 (mod 3) e b ≡ 2 (mod 3). Dessa forma, { a ≡ 3 ≡ 3 b ≡ 3 ≡ 3 ⇒ a 2 + b 2 ≡ 2 (mod 3) ⇒ 3  a 2 + b 2 (Absurdo!). É, então, absurdo supor que 3  a ou 3  b, então 3 | a e 3 | b. ∎

24. Mostrar que se p e q são primos, p  q  5, então p2  q2 ≡ 0 (mod 24).

1. Mostrar que 47 | 223  1. Para mostrar que 47 | 223  1, devemos mostrar que 2^23 ≡ 1 (mod 47). Notemos que 2^10 = 1024 = 37 + 47  21. Ou seja, 2^10 ≡ 37 (mod 47) ⇒ 2^10 ≡ 10 (mod 47). Então, [2^10]^2 ≡ (10)^2 (mod 47) ⇒ 2^20 ≡ 100 (mod 47) ⇒ 2^20 ≡ 6 (mod 47) (I) Vejamos, agora, que 2^3 = 8 = 47  39, ou seja, 2^3 ≡ 39 (mod 47) (II). De (I) e (II), (2^20  2^3) ≡ 6  (39) (mod 47) ⇒ 2^23 ≡ 234 (mod 47). Mas, 234 = 1  47  5, então 2^23 ≡ 1 (mod 47).

a) II and IV are correct.
b) II, III, and IV are correct.
c) I, III, and IV are correct.

2. Encontrar o resto da divisão de 734 por 51 e o resto da divisão de 563 por 29. i) Vejamos que 7^2 ≡ 2 (mod 51). Então, (7^2)^17 ≡ (2)^17 (mod 51) ⇒ 7^34 ≡ 2^17 (mod 51). (I) Porém, ≡ ≡ } ⇒ 2^10  2^7 ≡ 4  26 (mod 51) ⇒ 217 ≡ 104 (mod 51) ⇒ 2^17 ≡ 2 (mod 51). Dessa forma, 2^17 ≡ 2 (mod 51) ⇒ 2^17 ≡ 49 (mod 51). (II) De (I) e (II), temos que 7^34 ≡ 49 (mod 51), o que indica que o resto da divisão de 7^34 por 51 é 49. ii) Notemos que 5^3 ≡ 9 (mod 29), o que nos dá: 5^63 ≡ 9^21 (mod 29). Como 9 = 3^2, 5^63 ≡ 3^42 (mod 29) (I) Mas, 3^3 ≡ 2 (mod 29) ⇒ 3^42 ≡ (2)^16 (mod 29) ⇒ 3^42 ≡ 2^16 (mod 29) (II) No entanto, 2^8 ≡ 13 (mod 29) ⇒ (2^8)^2 ≡ 13^2 (mod 29) ⇒ 2^16 ≡ 169 (mod 29) ⇒ 2^16 ≡ 24 (mod 29) (III). De (I), (II) e (III), temos que 5^63 ≡ 24 (mod 29), ou seja, o resto da divisão de 5^63 por 29 é 24.