Déterminer le reste de la division euclidienne d'une puissance

Bonjour,

J'aurai besoin de votre aide pour reussir à faire un exercice.
On nous demande tout d'abord de determiner le reste de la division euclidienne de 5^4 par 13, je trouve 1.
Ensuite, on nous dit Démontrer que si n=4k+r où k et r sont des entiers naturels avec 0 ≤ r < 4, alors 5^n ≡ 5^r [13] ?
Estce que mon résultat de la premiere question est bon ? et pouvez vous me mettre sur la piste pour la deuxieme s'il vous plait.

Merci d'avance.
Loris

Bonjour,
Le premier résultat est juste. Pour le second, calcule $5^n$ en utilisant le fait que n = 4k+r

On trouve $5$ ^n $5^{4k}$ × $5^r$ ? mais aprés comment faire ?

$5^{4k}$ = $(5$ ^4 $^k$
Et $5^4$ ≡ 1 modulo 13

ah d'accord ! merci beaucoup.
La question d'aprés nous demande d'en déduire en fonction des valeurs de n, le reste de la division de $5^n$ par 13, et j'ai trouvé que r pouvait etre egal à 0, 1, 2 ou 3, donc les restes de $5^n$ par 13 en fonction de n sont bien , 1, 5, 25 ou 125 ?
Et j'aurai besoin d'un petit rappel sur les entier s'écrivant en base 5?

Merci beaucoup.
Loris

Les restes sont forcément inférieurs à 13, donc tu dois prendre tes résultats modulo 13
$5^0$ ≡ 1 modulo 13
$5^1$ ≡ 5 modulo 13
$5^2$ ≡ ? modulo 13
$5^3$ ≡ ?? modulo 13

$5^2$ ≡ 12 et $5^3$ ≡8 ?

Oui
La réponse est donc ( on te demande en fonction de n ) :
Si le reste de la division de n par 4 est 0 , alors le reste de la division de $5^n$ par 13 est 1 ;
Si le reste de la division de n par 4 est 1 , alors le reste de la division de $5^n$ par 13 est 5 ;
etc ...

Et que veux-tu savoir sur l'écriture d'un nombre ( entier ? ) en base 5 ?

okay d'ac !

Et pour la base 5, est ce que ca marche comme cela, c'est à dire, 0 1 2 3 4 , 10 11 12 13 14 , 20 21 22 23 24 ... ?

oui, en ajoutant 1 à chaque fois, et sachant que cinq s'écrit 10.

Désolé j'ai pas compris le "en ajoutant 1 à chaque fois" ?

Je me suis mal exprimé : c'est toi qui ajoute 1 à chaque fois pour fabriquer
tesexemples :
0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
1 + 3 = 4
1 + 4 = 10
1 + 10 = 11
etc...

ah oui d'accord ^^
Et comment prouver qu'un entier ecrit en base 5 sous la forme abcd est divisble par 15 si et seulement si (d-b) + 5(c-a) est divisible par 13 ?
J'ai éssayé de développer (d-b) + 5(c-a) mais ca ne mene à rien...

Merci beaucoup

Si le nombre x s'écrit abcd , cela signifie que
x = d + 5c + $5^2$ b + $5^3$ a
Cherche à quoi x est congru modulo 13

On remplace par les restes trouvés avant ? c'est à dire x ≡ 8a + 12b + 5c + d [13] ?

Oui.
Mais on utilise une "astuce" : 12 est congru aussi à un nombre
simplemodulo 13.
8 également.

12 ≡ -1 [13] et 8 ≡ -5 [13] ?

Oui, remplace

ah oui d'accord , on trouve x ≡ -5a + (-b) + 5c + d, donc x ≡ (d-b) + 5(c-a) !
Et d'écrire prouve que cest si et seulement si (d-b) + 5(c-a) est divisble par 13 alors abcd aussi ?

et donc pour la question suivante, "Pour tout n ∈ N, on pose $U_n$ = $5^{3n}$ + $5^{2n}$ + $5^n$ + 1. Démontrer que $U_n$ est divisible par 13 si et seulement si, n n'est pas divisible par 4."

J'ai donc fait comme avant , $U_n$ ≡ $8^n$ + $12_n$ + $5_n$ + 1 [13] mais je ne sais pas s'il faut remplacé par -5 et -1 ? ou faire autrement ?

Citation
Et comment prouver qu'un entier ecrit en base 5 sous la forme abcd est divisble par
15si et seulement si (d-b) + 5(c-a) est divisible par 13 ?
Par 15 ou par 13 ?

Par 13! désolé !

Dans ce cas la question est réglée.

Pour Un = $5^{3n}$ + $5^{2n}$ + $5^n$ + 1, tu as déjà :
si n est divisible par 4 , alors à quoi Un est-il congru modulo 13 ?

Je vois pas du tout comment faire ... je suis bloquée à $U_n$ ≡ $8^n$ + $12^n$ + $5^n$ + 1 [13]

Garde l'écriture donnée.
Si n est multiple de 4 alors que peux-tu dire de 3n , de 2n ?

n multiple de 4 , alors 3n multiple de 12 et 2n multiple de 8 ?

Plus simplement : ce sont des multiples de 4.
Dans ce cas , à quoi est congru Un modulo 13 ?

Je ne vois pas du tout ...

Sachant que 3n est un multiple de 4 , que peux tu dire de $5^{3n}$ modulo 13 ?

c'est aussi un multiple de 4 ?

Non. Tu dois utiliser le résultat de la première question :
3n = 4k + 0 ici
donc $5^{3n}$ ≡ ?, modulo 13

$5^{3n}$ ≡ $5^{4k}$ [13] ? ...

Oui, mais le calcul a déjà été fait : $5^{4k}$ ≡ ? modulo 13

$5^{4k}$ ≡ 1 [13]

Donc $5^{3n}$ ≡ 1 [13]

C'est ça.
Même chose pour les autres termes.
Donc Un ≡ ? modulo 13

Donc Un ≡ 4 [13] ?

Oui, ce qui fait que ce ne peut pas être un multiple de 13.
Je résume :
si n est un multiple de 4 , alors Un n'est pas un multiple de 13.
Autrement dit :
Si Un est un multiple de 13, alors n n'est pas un multiple de 4.
C'est la première partie de ce que tu dois démontrer.

Maintenant, il faut établir la réciproque : tu dois démontrer que si n n'est pas un multiple de 4 , alors Un est un multiple de 13.
A toi.

Mais il y a quelque chose que ne comprends pas, c'est peut-être tout simple mais si Un ≡ 4 [13], pourquoi Un n'est pas un multiple de 13 ? et pour établir la réciproque il faut faire la meme chose ?

Merci.

et j'ai admis le fait que 3n = 4k + 0, comme tu dis plus haut, mais je ne vois pas pourquoi ? Tu dis que je dois utiliser le résultat de la premiere question mais je ne comprends pas le raisonnement ..