Indicatrice d'Euler et congruence
dans Arithmétique
Bonsoir,
Je bloque à la question $1$. Voici ce que j'ai fait.
Soit $k \in \Z$ et $a \in \Z$.
Pour la question 1, je pose $n=p_1 \times \cdots \times p_r$ avec $\forall i \in [|1,r|] \ p_i \in \mathcal P$.
Ainsi $\varphi(n)=\varphi(p_1 \times \cdots \times p_r)=\varphi(p_1) \times \cdots \times \varphi (p_r)=(p_1-1) \times \cdots (p_r-1)$.
Alors $a^{1+k \varphi(n)}=a^{1+k (p_1-1) \times \cdots (p_r-1)}$
Je ne vois pas comment avancer.
Je bloque à la question $1$. Voici ce que j'ai fait.
Soit $k \in \Z$ et $a \in \Z$.
Pour la question 1, je pose $n=p_1 \times \cdots \times p_r$ avec $\forall i \in [|1,r|] \ p_i \in \mathcal P$.
Ainsi $\varphi(n)=\varphi(p_1 \times \cdots \times p_r)=\varphi(p_1) \times \cdots \times \varphi (p_r)=(p_1-1) \times \cdots (p_r-1)$.
Alors $a^{1+k \varphi(n)}=a^{1+k (p_1-1) \times \cdots (p_r-1)}$
Je ne vois pas comment avancer.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Soit $a \in \Z$ premier avec $n$. Alors sa classe appartient au groupe des inversibles de l'anneau $\Z / n \Z$. Ce groupe étant de cardinal $\varphi(n)$, on en déduit que l'ordre de $\bar{a}$ divise $\varphi(n)$. Donc $\bar{a}^{\varphi(n)}=\bar{1}$ donc $a^{\varphi(n)} \equiv 1[n]$.
Si $a$ est premier avec $n$ alors d'après le théorème d'Euler démontré ci-haut, $a^{\varphi(n)} \equiv 1[n]$.
Ainsi $a^{k \varphi(n)} \equiv 1^k [n] \equiv 1 [n]$ et donc $$\boxed{a^{1+k \varphi(n)} \equiv a [n]}$$
Si $a$ n'est pas premier avec $n$, je ne vois pas comment faire :-S
donc $a^{1+k\phi(n)}=a^{1+(p_i-1)k\prod(p_j-1)}=a\:1^{k\prod(p_j-1)}=a\bmod{p_i}$.
Pareillement posons $n=\prod p_i^{r_i}$. D'après le théorème d'Euler $x^{\phi(n)}=1\bmod n$ et il suffit donc de prouver que $a^{1+k\phi(n)}=a\bmod{p_i^{r_i}}$ et comme $\phi$ est multiplicative c'est la même preuve qu'avant (en raccourcissant l'écriture)
$a^{1+k\phi(n)}=a^{1+k\prod\phi(p^r)}=a^{1+\phi(p^r)\,k\prod\phi(p'^r)}=a\bmod{p^r}$
Le résultat est faux si $a\wedge n\neq1$ par exemple $3^{1+6}=0\bmod 9$
Ca fonctionne avec un produit de premiers distincts parce que si $a$ n'est pas un multiples de $n$ (auquel cas tout est nul !) il y a au moins un $p$ divisant $n$ avec lequel $a$ est premier; du coup modulo $p$ ou bien $a$ est premier avec $p$ et l'on a Fermat ou bien $a=0$ et ça marche encore.
De toute façon je ne voulais pas la solution mais juste des indications.
Le petit théorème de Fermat dit que pour tout nombre premier $p$ et pour tout $a \in \Z \ a^p \equiv a [p]$
Je ne vois pas comment on peut l'appliquer ici.
$n=p_1 \times p_2 \times \cdots \times p_r$ avec les $p_i$ premiers donc à fortiori premiers entre eux.
On prend l'isomorphisme $\boxed{\phi : \Z / n \Z \longrightarrow \Z / p_1 \Z \times \Z / p_2 \Z \times \cdots \times \Z / p_r \Z \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [q]_{n} \mapsto ([q]_{p_1} , \cdots, [q]_{p_r})}$
Or $\boxed{\varphi(p_1)=p_1-1}$.
Je dois montrer que $a^{1+k \varphi(p_1)} \equiv a [p_1]$
Mais $1+k \varphi(p_1)=1+ k(p_1-1)$ alors $a^{1+k \varphi(p_1)} =a^{1+ k(p_1-1)} $
D'après le petit théorème de Fermat, $a^{p_1} \equiv a[p_1]$
Ainsi $a^{k p_1} \equiv a^k [p_1]$
Et donc $a^{1+k \varphi(p_1)} \equiv a^{1-k} a^k [p_1]$
De même, on montre que $\boxed{\forall i \in [|1,r|] \ a^{1+k \varphi(p_i)} \equiv a [p_i]}$
A ce stade je bloque pour appliquer le théorème des restes chinois.
On peut donc considérer $k >0$.
À présent tu peux en déduire la valeur de $a^{1+k \varphi(n)}$ modulo $p_i$ pour $i \in [|1,r|]$, sachant que $\varphi(n)=(p_1-1) \times \cdots (p_r-1)$.
Ensuite tu pourras terminer avec le th. des restes chinois.
PS. il y a également la remarque de nahar, qui n'invalide pas ton résultat mais qui demande peut-être une petite justification dans ton argument.
Je suis bloqué.
Puis occupe-toi seulement de la relation entre $a^{k (p_i-1)}$ et $a^{k (p_1-1) \times \cdots \times (p_r-1)}$.
Si $p_i$ divise $a$ alors $a \equiv 0 [p_i]$ et $a^{1 + k (p_i-1)} \equiv 0[p_i]$ il y a égalité.
Si $p_i$ ne divise pas $a$, alors $p_i$ est premier avec $a$. Car un nombre premier est premier avec tous les entiers qu'il ne divise pas.
Ainsi $a$ est inversible dans $\Z / p_i \Z$ ce qui donne $\boxed{a^{k(p_i-1)} \equiv 1 [p_i]}$
On en déduit $a^{k \varphi(n)} \equiv 1^r [p_i]$ donc $\boxed{a^{k \varphi(n)} \equiv 1 [p_i]}$
On a donc le système de congruences :
$\begin{cases}
a^{k \varphi(n)} \equiv 1 [p_1] \\ \cdots \\ a^{k \varphi(n)} \equiv 1 [p_r] \end{cases}$
Je n'arrive pas à appliquer le théorème des restes chinois ici :-S
Sinon je ne connais pas le théorème des restes chinois.
Pour moi si $a$ et $b$ divisent $c$ et sont premiers entre eux alors $ab$ divise $c$.
Je ne connais pas ce résultat Nahar.
Je bloque à ce stade :
$\begin{cases} a^{1+k \varphi(n)} \equiv a [p_1] \\ \cdots \\ a^{1+k \varphi(n)} \equiv a [p_r] \end{cases}$
Le théorème des restes chinois donne que les solutions du système sont les entiers congrus à $ a^{1+k \varphi(n)}$ modulo $n$.
Je ne vois pas comment en déduire le résultat voulu.
$\forall i \in [|1,r|] \ a^{1+k \varphi(p_i)} - a $ est divisible par $p_i$ te permettra de conclure.
OK et tu vois que $a$ est aussi une solution du système, donc...
PS. on peut aussi procéder comme le suggère nahar ici http://www.les-mathematiques.net/phorum/read.php?5,2180940,2181488#msg-2181488
C'est le but de mon exemple : avec $n=9,\ \phi(n)=6,\ a=3$ et le résultat proposé est manifestement faux pour tout $ k\neq0$.
l'énoncé demande que $n$ soit produit de nombre premiers distincts.
En plus je ne comprends rien à ce que vous écrivez.
RaoulS
En effet pour le système car $a \equiv a [p_i]$.
Comme le suggère Nahar je ne vois pas comment avancer. Comment on passe de $a^{1+ k \varphi(p_i)}-a$ divisible par $p_i$ à $a^{1+ k \varphi(n)}-a$ divisible par $n$ ?
Le résultat dont j'ai parlé plus haut est juste un corollaire du théorème de Gauss.
Je cherche la question 2 maintenant.
Je prends $n=8=4 \times 2$ qui n'est pas le produit de nombres premiers distincts.
Calculons $\varphi(8)= card \{ k \in [|1,8|] \ | \ PCGD(k,8)=1 \}=7 $
Donc $a^{1+ k \varphi(8)}=a^{1+7k}$
Prenons $a=3$ alors $a^{1+ k \varphi(8)}=a^{1+7k}=3^{1+7k}=3 \times 3^{7k}$ où $3^7=2187=8 \times 273+3$
$3^7 \equiv 3 [8]$ donc $3^{7k} \equiv 3^k [8]$
Donc $a^{1+ k \varphi(5)} \equiv 3 \times 3^k [8] \equiv 3^{k+1} [8] $
Alors que $3 \equiv 3 [8]$
Si on prend $k=2$ on a $3^{k+1} = 9 \equiv -1 [8] \not\equiv 3 [8]$
Ensuite tu compliques encore les choses: quelle est la négation de la proposition du 1)?
Et enfin noradan t'a déjà donné un contre-exemple.
Et de nouveau enfin arrête de vouvoyer tout le monde ou du moins arrête de me vouvoyer.
Ok je corrige mon erreur d'étourderie, c'est $\boxed{\varphi(8)=4}$ car seuls $1,3,5,7$ sont premiers avec $8$.
La négation est :
si $n$ n'est pas le produit de nombres premiers distincts alors $\exists k \in \Z, \ \exists a \in \Z ,\ a^{1+ k \varphi(n)} \not\equiv a [n]$
Soit $a=2$ et $k=1$.
On a $a^{1+ k \varphi(8)}=a^{1+4k}=2^5 \equiv 0 [8]$ alors que $2 \equiv 2 [8]$
Je tombe sur ce post. Peut-on dire que $\forall p \mid n,\ p$ premier, $\ \forall a \in \mathbb{Z},\ a^{1+k \varphi(n)}=a\ $ dans $\mathbb{Z} / p \mathbb{Z}$ (car si $pgcd(a,p)=1$, alors $a ^{ \varphi(p)}=1$ dans $\mathbb{Z} / p \mathbb{Z}$, et comme $\varphi(p) \mid \varphi(n)$, alors $a^{1+k \varphi(n)}=a$ dans $\mathbb{Z} / p \mathbb{Z}$ ; et si $pgcd(a,p) \ne 1$, alors $p \mid a$, donc $a^{1+k \varphi(n)}=a=0$ dans $\mathbb{Z} / p \mathbb{Z}$).
Puis avec le théorème chinois, vu l'isomorphisme entre $\mathbb{Z} / n \mathbb{Z}$ et le produit des $\mathbb{Z} / p \mathbb{Z}$ pour $p$ divisant $n$, on a bien $a^{1+k \varphi(n)}=a$ dans $\mathbb{Z} / n \mathbb{Z}$.