Comment savoir le reste d'une division euclidienne simplement

[iPEKKAble]

Bonjour,
Je viens d'entrer en fac de maths, et pendant un cour on a brièvement abordé la division euclidienne, ( douloureux rappel de la spé maths experte ) Et j'ai trouvé quelques astuces que j'aimerai partager pour savoir si elle est viable ou non. Mon astuce réside principalement sur un chiffre de la forme $a^x$ auquel on assimilerai un diviseur quelconque noté ici b. ( Prenons un exemple pour que cela soit plus parlant .

Imaginons que je vous demande de me calculer le reste de la division euclidienne de $7^{13456889}$ par 5 (j'ai fait exprès de prendre un chiffre assez conséquent que la calculatrice ne puisse pas l'atteindre )
Ainsi il nous est impossible de poser $7^{13456889}/5$

Bien,
Désormais on se retrouve un peu bloqué, ce que je vais faire c'est établir un cycle des multiple des puissances de 7.
exemple : $7^1$ = 7 ( jusque la normalement ça va)
$7^2$ = 7×7
$7^3$ =7×7×7
$7^4$ = $7^3$×7
$7^5$ = $7^4$ × 7
$7^6$ = $7^5$ × 7
Pour établir ce cycle on va juste regarder le chiffre des unité qu'on obtient et le multiplier par 7
Cela nous donne donc :
$7^2$ = 7×7 = 49 donc on retient 9
$7^3$ = 7 × 9 = 63 donc on retient 3
$7^4$ = 7 × 3 = 21 donc on retient 1
$7^5$ = 7 × 1 = 7 donc on retient 7
Je me base ici sur le fait que le reste n'est basé que sur le chiffre des unités ainsi comme on sait que 5k va de 5 en 5 et qu'il se termine toujours pas un 5 ou un 0 pour un k ∈ Z
donc imaginons que $7^n$ = 8654874 ( fantaisiste ) alors on sait que le reste est de 4 puisque le plus proche multiple de 5 sera 5k = 8654870 + 4 = $7^n$

Revenons à notre cycle, donc on a :
$7^1$ => se termine par 7
$7^2$ => se termine par 9
$7^3$ => se termine par 3
$7^4$ => se termine par 1
$7^5$ => se termine par 7
$7^6$ => se termine par 9

Les plus malin on déjà vu ou je veux en venir, on viens d'obtenir notre cycle de "récurrence" pour tout $7^n$ que je marque en gras ci-dessus, formé de 4 terme.
On a donc un cycle de 4 terme qui s'opère ainsi pour tout $7^n$ il va être de la forme $7^{n+4k^{\prime }}$ avec n ∈ 1;2;3;4
Je fais un petit exemple pour que ça soit plus clair:
imaginons $7^{20}$ et on cherche le reste de sa division euclidienne par 5.
On reprend notre formule $7^{n+4k^{\prime }}$ avec n ∈ 1;2;3;4 et on cherche une équation vérifiant n+4k'=20, or on sait désormais que n peut-être soit 1; 2; 3 ou 4 vous trouvez en 30 sec que la seule solution possible est 4.
puisqu'on obtient avec 1;2 et 3 un k' ∉ Z
Autrement, plus simplement dit vous auriez pu partir de $7^4$ en montant les puissance de 4 en 4
ce qui nous donne $7^8$ se termine par 1
$7^{12}$ se termine par 1
$7^{16}$ se termine par 1
$7^{20}$ se termine par 1 soit pile ce que l'ont voulait
maintenant rien de plus simple, plus qu'a conclure:
Soit r le reste de la division euclidienne de $7^{20}$ par 5 ainsi comme le chiffre des unités de $7^{20}$ est 1 le reste sera de 1 comme la valeur de 5k la plus proche de $7^{20}$ se termine par un 0 on fait +1 pour l'atteindre.
Avec ce raisonnement revenons à notre chiffre de $7^{13456889}$ :
On a donc n+4k' = 13456889 on teste avec les valeurs de n possible successives :
Et on trouve que n =1 car pour n = 2 ; 3 ; 4 k' ∉ Z
donc $7^{13456889}$ se termine par un 7 et donc la valeur de 5k la plus proche se termine par un 5 ainsi on peut dire :
Soit r le reste de la division euclidienne de $7^{13456889}$ par 5, ainsi on a démontré que r = 2
on a donc 5k + 2= $7^{13456889}$ avec k inconnu puisque ma calculatrice ne peut pas l'atteindre.

Vous l'aurez compris grâce à cela on peut calculer pour n'importe quel reste de la division de $7^b$ par 5 tant que vous savez résoudre n+4k' = b avec n soit 1,2,3,4 et k' entier. et le but n'est pas vraiment de savoir combien fait k' mais juste de savoir si il est entier,
par exemple pour n = 13456889 ci-dessus c'est assez dur de le faire de tête donc si vous connaissez vos règles de divisibilité pour 4 ça le fait,
je vais détailler encore un peu plus : soit n+4k' = 13456889
On test pour n=2
ce qui fait $\frac{13456887}{4}$=k' or vous savez que pour qu'un chiffre soit divisible par 4 la somme des 2 derniers chiffres doit être un multiple de 4, ainsi on a 8+7 = 15 ( le calcul le plus dur a faire ici )
j'espère que vous savez que 15 n'est pas dans la table de 4
vous faite la même chose pour n=1;3;4 et vous trouvez qu'il n'y a que 1 qui marche car 8+8 = 16 = 4 × 4

Les faiblesses de cette méthode :
Quand j'ai pensé à la réalisation de cette méthode je me suis heurté et je me heurte toujours à des problèmes déjà l'équation phare de cette méthode qui est n + 4k' = b dépend énormément de l'indice, ici on avait 7 et on observé que le cycle des puissances de 7 "se reset" de 4 en 4 mais si on avait $8^{13456889}$ par 5 cela aurait été totalement différent ( je vous laisse le faire si vous avez réussi à comprendre la méthode )

1. Chaque chiffre possède son propre terme qui remet la séquence des nombres entier au départ, ici c'était 4 mais 23 peut très bien avoir une séquence de 18 terme ( fantaisiste) avant de retomber sur le chiffre des unité vu avec $23^1$
2. Le problème du diviseur s'impose lui aussi, en effet j'ai pris 5 comme diviseur pour me simplifier la tache car on sait qu'il est constant et va de 5 en 5 mais si j'avais pris 9 la tache aurait déjà été beaucoup plus ardu, ce qu'il faudrait faire c'est établir une récurrence pour chaque diviseur possible, mais cela prendrai énormément de temps ( j'estime à l'heure actuelle une trentaine d'heure ) à moins de découvrir quelque chose qui nous simplifie la tache. Mais à terme si cela s'effectue on pourra calculer pour toute division euclidienne de $X^n$ par y en moins que 2 minute même avec un $X^n$ inatteignable par la calculatrice.
   Je sais que c'est long et que ça peut donner l'impression d'être beaucoup plus long que 2 minutes mais je reprend une dernière fois l'exemple de départ :

Calculer le reste de la division euclidienne de $7^{13456889}$ par 5
On a donc n+4k' = 13456889 on teste avec les valeurs de n possible successives :
Et on trouve que n =1 car pour n = 2 ; 3 ; 4 k' ∉ Z ( règle de divisibilité ci-dessus )
donc $7^{13456889}$ se termine par un 7 et donc la valeur de 5k la plus proche se termine par un 5 ainsi on peut dire :
Soit r le reste de la division euclidienne de $7^{13456889}$ par 5 est égal à 2.

C'est tout ce qu'on aurai à écrire si on savait le cycle de 7 à l'avance ( et même si on ne le sait pas à l'avance le calcul de sa "suite" ne nous prendrai que 10 min grand maximum).
Merci de m'avoir lu jusqu'au bout, des erreurs se sont sans doute glissé par ci-par la, merci d'apporter un regard critique à cette méthode encore très limité, ( venez pas me taper parce que vous l'avez fait en exam et que ça n'a pas marché )

[iPEKKAble]

@iPEKKAble by L.cds

[Black-Jack]

Bonjour,

Désolé, pas tout lu, c'est trop long pour moi.

"8^13456889 par 5 cela aurait été totalement différent ..."

Je fais ainsi :

8^0 / 5 --> Reste = 1
8^1 / 5 --> Reste = 3
8^2 / 5 --> Reste = 4
8^3 / 5 --> Reste = 2
8^4 / 5 --> Reste = 1
8^5 / 5 --> Reste = 3
...

Donc :
Si l'exposant est = 4k, le reste est 1
Si l'exposant est = 4k+1, le reste est 3
Si l'exposant est = 4k+2, le reste est 4
Si l'exposant est = 4k+3, le reste est 2

13456889 = 3364222*4 + 1

L'exposant est donc = 4k + 1 ---> le reste est 3

[iPEKKAble]

@Black-Jack
Bonjour, je trouve exactement comme vous, j'avoue que l'exemple était un mal choisi comme on garde un cycle de 4k avant de retomber sur le même reste comme pour 7,
Comme exemple on aurait pu prendre 9^n qui aurait été plus judicieux puisqu'il possède un cycle différent de 7, c.à.d. 2k ( ce qui est le rend encore plus simple) si on reste en division euclidienne par 5.

[Black-Jack]

@iPEKKAble a dit dans Comment savoir le reste d'une division euclidienne simplement :

@Black-Jack
Bonjour, je trouve exactement comme vous, j'avoue que l'exemple était un mal choisi comme on garde un cycle de 4k avant de retomber sur le même reste comme pour 7,
Comme exemple on aurait pu prendre 9^n qui aurait été plus judicieux puisqu'il possède un cycle différent de 7, c.à.d. 2k ( ce qui est le rend encore plus simple) si on reste en division euclidienne par 5.

(9^n)/5

9^0 / 5 --> Reste = 1
9^1 / 5 --> Reste = 4
9^2 / 5 --> Reste = 1
9^3 / 5 --> Reste = 4
...
Si n est pair, le reste est 1
Si n est impair, le reste est 4

Exemple, quel est le reste de le division de 9^113 par 5 ?
113 est impair et donc le reste de la division de 9^113 par 5 est 4

Si n est impair, le reste est 4