Calculer la somme de tous les éléments de $\Z/n\Z$

Chaurien

Voir la parité de $n$, et factoriser $x^4+4y^4$.

NicoLeProf

Pour le moment, je trouve que $n=1$ pour avoir $n^4+4^n$ premier.

Pour $n$ pair, on voit directement que $n^4+4^n$ est divisible par $2$ (et strictement plus grand que $2$) donc ne peut pas être premier.

Pour $n$ impair non divisible par $5$, on peut démontrer que $n^4+4^n$ est divisible par $5$ en raisonnant modulo $5$.

Mais si $n$ est impair et divisible par $5$, là...

Pour $n=5$, $5^4+4^5=1649$ et c'est divisible par $17$ donc non premier...

Mais pour les autres???

Chaurien

Relire mon indication.

Fin de partie

@Amadou:

Pour $n$ pair je cherche les entiers $a$ qui sont leur opposé modulo $n$. On en connaît deux, $0$ et $n/2$ (c'est un entier, $n$ est pair) mais a priori il pourrait il y en avoir d'autres.

$a\equiv -a \mod{n}$ est équivalent à $n$ divise $2a$ mais ne pas oublier que $0\leq a<n$ donc $0\leq 2a<2n$ or, les seuls multiples positifs de $n$ strictement inférieurs à $2n$ sont $0$ et $n$ donc si $2a$ est multiple de $n$ alors il ne peut être égal qu'à $0$ ou $n$. Ces deux cas sont possibles ils correspondent à $a=0$ et $a=n/2$ et donc la somme cherchée vaut $n/2$.

Pour $n$ impair, le théorème de Gauss permet de conclure rapidement.

Si $n$ divise  $2a$ et que $n$ est impair, donc $n$ et $2$ sont premiers entre eux, donc $n$ divise $a$ mais ce n'est possible que si $a=0$ car $0\leq a<n$. Ce qui fait qu'il y a qu'un seul élément qui est son propre opposé modulo $n$ c'est $0$ et ainsi la somme cherchée est nulle.

PS:

Plus haut, JLT a développé une solution qui est peut-être plus simple.

Quand on travaille modulo $n$ on n'est pas obligé de prendre pour représentant de chaque classe d'équivalence les nombres $0,1,...,n-1$

Tout autre ensemble de $n$ entiers qui ne sont pas congrus deux à deux convient. Pour calculer la somme cherchée il suffit de prendre un tel système mieux adapté que le système de représentants habituels.

Si $n$ est pair, on peut prendre comme système de représentants l'ensemble $\{-n/2+1,...,n/2\}$ cet ensemble contient $n/2-(-n/2+1)+1=n$ éléments et il est clair que si un élément sauf $n/2$ appartient à cet ensemble, son opposé (au sens de l'addition des nombres entiers relatifs) appartient aussi à cet ensemble et, sauf $0$, aucun n'est son propre opposé.

Si $n>1$ est impair on peut prendre comme système de représentants l'ensemble $\{-(n-1)/2,..,(n-1)/2\}$

Ben314159

Une fois traité le cas évident où $n$ est pair (et éventuellement regardé les congruences modulo 5, mais ce n'est pas indispensable), on peut se dire que, vu que $n^4\!=\!\big(n^2\big)^{\!2}$ et que $4^n\!=\!\big(2^n)^2$, il faudrait peut-être évaluer $\big(2^n\!+\!n^2\big)^{\!2}$ . . .

Oupss : désolé, je n'avais pas vu qu'il y avait deux pages dans le fil et que mon "indication", ça fait un bail qu'elle a été donnée . . .

Chaurien

Pour trouver les $n \in \mathbb N^*$  tels que $n^4+4^n $ soit premier, j'ai préconisé de regarder la parité de $n$ et de factoriser $x^4+4y^4$. 

Bis repetita placent.

J'ai voulu proposer un exercice qui utilise les calculs algébriques, comme celui qui fait prouver que $b^5+b^4+b^3+b^2+b+1$ n'est pas premier.

Julia Paule

$n^4+4^n=(n^2+2^n)^2-2^{n+1}n^2$.
Pour $n$ pair, on a vu que c'est réglé : pas premier.
Pour $n$ impair, on pose $n+1=2m$, on a une différence de deux carrés, qui se factorise. Il y a un cas particulier pour $n=1$.

JLT

Généralisation de l'exercice initial : si $a\geqslant 2$ et $n\geqslant 2$ sont des entiers tels que $n$ est composé, alors $1+a+\cdots+a^{n-1}$ n'est pas premier.

Amadou

@Fin de partie

Merci vraiment beaucoup tout est clair pour maintenant pour moi. 
J'ai bien compris.

Amadou

@Chaurien après calcul en donnant des valeurs à $n$ (impair) je trouve que pour tout $n\le207$ il n'y a pas de nombre premier. 

Amadou

@Chaurien merci pour l'indication

Amadou

@JLT
En fait je ne sais pas si j'ai vraiment très bien compris votre phrase. Mais si $a=6$ et $n=8$ alors $1+6+6^2+6^3+6^4+6^5+6^6+6^7=335917$ qui est premier.

troisqua

@JLT ma solution : on a, en notant $p,q$ deux nombres premiers, $m$ un naturel et $n=pqm$, le fait que $\Phi_{p}\left(a\right)\Phi_{q}\left(a\right)$ divise $S=\prod_{\begin{subarray}{c} d|n\\ d>1 \end{subarray}}\Phi_{d}\left(a\right)$. Mais $S=\sum_{i\in n}a^{i}$. Or, $p$ et $q$ étant premiers, l'expression connue de $\Phi_{p}$ et $\Phi_{q}$ montre que $\Phi_{p}\left(a\right)$ et $\Phi_{q}\left(a\right)$ sont plus grands que $1+a\geqslant 2$. Donc $S$ est composé. $a$ naturel non nul suffisait.

Ben314159

Amadou a dit : @JLT
En fait je ne sais pas si j'ai vraiment très bien compris votre phrase. Mais si $a=6$ et $n=8$ alors $1+6+6^2+6^3+6^4+6^5+6^6+6^7=335917$ qui est premier.

Tu as raté le 6 :
$1+6+6^2+6^3+6^4+6^5+6^6+6^7\ =\ 335\,923\ =\  7\times 37 \times 1297$
Et concernant le résultat de @JLT, dans le cas où $n\!=\!15\!=\!3\!\times\!5$, si je t'écris que :
$1+a+a^2+\dots+a^{14}=(1+a+\dots+a^4)+(a^5+a^6+\dots+a^9)+(a^{10}+a^{11}+\dots+a^{14})$
est-ce que ça t'aide ?

JLT

Voici ma solution. Supposons que $n=uv$ avec $u,v\geqslant 2$. Alors $1+a+\cdots+a^{n-1}=(1+a+\cdots+a^{u-1})(a^u+a^{2u}+\cdots+a^{(v-1)u})$.

Chaurien

Amadou, revois ton calcul. Ta somme « $1+6+6^2+6^3+6^4+6^5+6^6+6^7=335 917$ » est fausse. Par une factorisation évidente, il est bien clair que pour $b \in \mathbb Z$ et $n \in \mathbb N^*$, la somme  $1+b+b^2+...+b^{2n-1}$ est divisible par $b+1$.

troisqua

@JLT : Jolie identité (vraie aussi quand $a=1$). La décomposition à l'aide des polynômes cyclotomiques a le mérite de faire apparaître beaucoup de facteurs.

troisqua

Exercice (généralisation) : Soient $a,n$ deux naturels non nuls tels que $1+a+\dots+a^{n-1}$ soit une puissance d'un nombre premier. Montrer que $n$ est une  puissance d'un nombre premier.

Amadou

Ben314159 a dit :

Tu as raté le 6 : $1+6+6^2+6^3+6^4+6^5+6^6+6^7\ =\ 335\,923\ =\  7\times 37 \times 1297$

Désolé j'ai dû mal calculer avec la calculatrice.

Ben314159 a dit :
Et concernant le résultat de @JLT, dans le cas où $n\!=\!15\!=\!3\!\times\!5$, si je t'écrit que :
$1+a+a^2+...+a^{14}=(1+a+...+a^4)+(a^5+a^6+...+a^9)+(a^{10}+a^{11}+...+a^{14})$
est-ce que ça t'aide ?

Donc si je comprends $n$ est donc un entier premier composé.

JLT

Amadou a dit :

Donc si je comprends $n$ est donc un entier premier composé.

Pas "premier composé" (qui ne veut rien dire) mais "composé". C'est écrit dans mon énoncé.

Chaurien

Réponse à JLT. Soient des entiers $a \ge 2$ et $n \ge 2$, l'entier $n$ étant composé, ce qui signifie : $n=pq$, $p \in \mathbb N$, $q \in \mathbb N$, $p \ge 2$, $q\ge 2$. Alors $1+a+...+a^{n-1}=\frac {a^n-1}{a-1}= \frac {(a^{p})^q-1}{a^p-1}· \frac {a^p-1}{a-1}$, nombre composé.

Amadou

@JLT je comprends

JLT

troisqua a dit :

Exercice (généralisation) : Soient $a,n$ deux naturels non nuls tels que $1+a+\dots+a^{n-1}$ soit une puissance d'un nombre premier. Montrer que $n$ est une  puissance d'un nombre premier.

Par contraposée : si $n$ n'est pas une puissance d'un nombre premier alors $n$ possède deux facteurs premiers distincts $u$ et $v$. D'après mon message précédent, $S=1+a+\dots+a^{n-1}$ est divisible par $\frac{a^u-1}{a-1}$. De même il est divisible par $\frac{a^v-1}{a-1}$. Il suffit de montrer que ces deux nombres sont premiers entre eux, ou encore que $\mathrm{pgcd}(a^u-1,a^v-1)=a-1$, ce qui est classique.