Introduction à la fonction Phi d'Euler

Question

Ceci est tiré du livre de théorie des nombres de Joseph Silverman.

Ceci est l'introduction avant de passer à la fonction Phi d'Euler.

---

Dans le chapitre précédent, nous avons prouvé le petit théorème de Fermat: si p est un premier et que p ne divise pas a, alors $a^{p-l} \equiv 1 \pmod p$. Cette formule n'est certainement pas vraie si on remplace p par un nombre composé. Par exemple,$5^5 \equiv 5 \pmod 6$ et $2^8 \equiv 4 \pmod 9$. On se demande donc s'il y a une certaine puissance, en fonction du module m, telle que$a^{???} \equiv 1 \pmod m$. Notre première observation est que cela est impossible si gcd (a, m)> 1. Pour voir pourquoi, supposons que$a^{k} \equiv 1 \pmod m$. ensuite$a^{k} = 1 + my$ pour un entier y, donc pgcd (a, m) divise $a^{k} -my = 1$. En d'autres termes, si une puissance de a est congruente à 1 modulo m, alors nous devons avoir pgcd (a, m) = 1.

---

Je n'arrive pas à comprendre les 2 dernières lignes ici

• ensuite $a^{k} = 1 + my$ pour un entier y, donc pgcd (a, m) divise $a^{k} - my = 1$.

Que signifie la ligne ci-dessus? $a^{k} - my = 1$est une équation. Comment gcd (a, m) peut-il diviser une équation?

Ensuite, je ne comprends pas comment la ligne suivante se produit également

• En d'autres termes, si une puissance de a est congruente à 1 modulo m, alors nous devons avoir pgcd (a, m) = 1.

Puis-je avoir une aide s'il vous plait?

Answer 1

Si $c \equiv 1 \pmod{b}$, alors ce que cela signifie $c-1 \equiv 0 \pmod{b}$ ou $c-1$ est un multiple de $b$.

Nous avons $a^k \equiv 1 \pmod{m}$, Par conséquent $a^k-1$ est un multiple de $m$, nous pouvons donc trouver un entier $y$ tel que $a^k-1 = my$.

Réorganiser l'équation, $$a^k - my =1$$

Pour $k \ge 1$, par la définition de diviseur commun, $\gcd(a, m)$ doit diviser $a$ et il doit aussi diviser $m$, donc il doit diviser $a^k-my$ qui est égal à $1$.

$\gcd(a,m)$ se divise $1$. Le seul entier positif qui divise$1$ est $1$.

Par conséquent $\gcd(a,m)$ doit être $1$.