Questão 5. (1,0) (a) Seja dado um número natural m = pα1 1 . . . pαr r decomposto em fatores irredutíveis. Seja n um número natural tal que ϕ(pαi ...

(a) Para provar que m divide an - 1 para todo número natural a primo com m, podemos usar o Teorema de Euler, que afirma que se a e m são primos entre si, então a elevado a função totiente de m é congruente a 1 módulo m. Como ϕ(pαi i) divide n para todo i = 1, . . . , r, temos que a elevado ϕ(pαi i) é congruente a 1 módulo pαi i para todo i. Portanto, a elevado n é congruente a 1 módulo m, o que implica que m divide an - 1. (b) Para mostrar que a12 - 1 é divisível por 4095 sempre que (a, 1365) = 1, podemos usar o Teorema de Euler novamente. Como 1365 = 3 x 5 x 7 x 13, temos que ϕ(1365) = 576. Portanto, se (a, 1365) = 1, então a elevado 576 é congruente a 1 módulo 1365. Além disso, a12 - 1 = (a6 + 1)(a6 - 1) = (a6 + 1)(a3 + 1)(a3 - 1). Como (a, 1365) = 1, temos que (a3 + 1) e (a3 - 1) são divisíveis por 1365. Além disso, como a elevado 576 é congruente a 1 módulo 1365, temos que a6 é congruente a 1 ou -1 módulo 1365. Portanto, a6 + 1 é divisível por 1365, o que implica que a12 - 1 é divisível por 1365 x 1365 = 4095.