Arithmétique (congruence)

[Piwatte]

Bonsoir,

Pour mon premier exercice, je dois déterminer le reste de 2015^2016 dans la division euclidienne par 6.

Je suis un peu bloqué surtout à cause de l'exposant 2016, je sais me débrouiller à trouver le reste d'un entier dans une division euclidienne, mais je suis un peu perdu en voyant la puissance.

Pour mon deuxième exercice, j'ai N=813 526, et je dois démontrer que N ≡ 6-2+5-3+1-8 (modulo 11)

Merci d'avance pour l'aide que vous pouvez me fournir

Un étudiant en détresse en maths

[mathelot]

bsr,
le modulo 6 étant compatible avec l'addition et la multiplication
on peut remplacer 2015 par 5
calcule le plus petit entier n tel que modulo 6

[Piwatte]

Je n'ai pas encore vu ça en cours, on ne fait que commencer, j'ai juste vu les "bases" en arithmétique, c'est pour ça que je demande quelques explications.

Sinon pour répondre, je dirais que le plus petit entier n est 2

[Ben314]

Salut,
C'est quoi que "tu as pas encore vu en cours" ?
Si c'est la première partie du message de mathelot alors... tu es mal...
Si c'est la deuxième partie de son message concernant le 5^n, il n'y a pas vraiment à "avoir vu ça en cours" : regarde les reste de division par 6 de 5^0 , 5^1 , 5^2, 5^3, ... jusqu'à par exemple 5^6 et tu comprendra ce qu'il a voulu t'expliquer.

Et sinon, c'est effectivement bien 2 le plus petit entier n tel que 5^n ait un reste de division par 6 égal à 1.

[Piwatte]

Par ce que je n'ai pas encore vu en cours, je parlais des puissances comme 2015^2016, d'où le fait que je demande de l'aide sur ce forum et aussi par la deuxième partie du message de mathelot concernant le 5^n, on a pas encore vu de méthode pour faire ça, donc j'arrive juste à donner le résultat en calculant de tête vu que le modulo est juste de 6, ce serait un modulo supérieur à 100, ce serait différent ..
Je n'arrive pas à comprendre comment je peux trouver le reste avec cet exposant ..

[Ben314]

Quand "on comprend pas trop", ben on commence par des truc plus simple pour... arriver à comprendre.
Donc tu commence par ça :

regarde les reste de division par 6 de 5^0 , 5^1 , 5^2, 5^3, ... jusqu'à par exemple 5^6...

que tu peut éventuellement mettre sous forme d'un tableau si ça t'amuse (1ère ligne : n= 0 1 2 3 4 5 6 ... ; 2em ligne : 5^n modulo 6 = ? ? ? ? ? ? ...)
et on reparlera ensuite du fait de savoir si c'est compliqué ou pas de savoir ce qu'il y aurait en dessous du 2016 si on faisait un immense tableau.
Éventuellement, si tu es pas trop familier avec, le 5^0, tu zappe en commençant à n=1 (en fait, 5^0 ça vaut 1)

[Piwatte]

J'ai un professeur qui refuse de corriger les exercices donc je galère comme tout le monde dans ma promo..
J'avais regardé, je te l'écris
5^0 = 1
5^1 = 5
5^2=25 (il reste 1)
5^3=125 (il reste 5)
5^4=625 (il reste 1)
5^5=3125 (il reste 5)
5^6=15625 (il reste 1)

Les exposants impairs ont les mêmes reste (soit le résultat de n^1), et les exposants pairs ont les mêmes restes également (soit le résultat de 5^0) ?
C'est ce que je dois comprendre ?

[Ben314]

Oui, c'est exactement ça et ça doit te permettre d'être "quasi sûr" que le reste de la division de 5^2016 par 6, ça va être 1 vu que 2016 est pair. (en Math, on appelle ça une "conjecture").
Voit tu comment faire "une vrai preuve mathématique" de ce résultat, c'est à dire du fait que tout les 5^n avec n pair donnent un reste de division par 6 égal à 1 ?
(et éventuellement du fait que tout les exposants impairs donnent un reste égal à 5, mais au fond ça on s'en fout vu qu'on veut juste connaitre le résultat pour l'exposant 2016 qui est pair)

Indication : Comment passe t'on d'un exposant pair a l'exposant pair suivant ?

[Piwatte]

On avait pas vu ça pourtant dans le cours, je te remercie, ça m'a aidé pour la suite de ma fiche d'exercices

Non, je vois pas comment je dois faire une "vraie preuve mathématique" de ce résultat par contre.. Je l'écris, mais je pense que au devoir je peux le présenter d'une façon bien meilleure.

Pour passer d'un exposant pair à l'exposant pair suivant, on le multiplie deux fois par le nombre soumis à la puissance ? (soit par un nombre au carré)

[Ben314]

Pour commencer par la fin, oui, on multiplie effectivement par le carré de la "base" de l'exposant.
Ici la "base", c'est 5, donc on multiplie par 5²=25 or modulo 6, 25 c'est 1 donc modulo 6, on multiplie par 1 ce qui signifie... qu'on ne fait rien et qu'on obtient le même reste que le coup d'avant.

Et c'est pour cette raison là que mathelot t'avais demandé de chercher le plus petit n tel que 5^n=1 modulo 6 : si ça avait été n=7 le plus n tel que 5^n=1 modulo 6, ça aurait signifié que dans la suite des 5^0, 5^1, 5^2, .... modulo 6, on aurait retrouvé "toute les 7 exposant" la même valeur vu que pour passer de 5^n à 5^(n+7), il faut multiplier par 5^7, c'est à dire par 1 modulo 6.

Sinon, concernant la présentation un jour de D.S., a mon avis (mais c'est évidement discutable), le truc le plus simple, c'est de faire un tableau avec n= 0 1 2 3 4 ... puis a^n modulo b = ? ? ? ? ? (le a et le b dépendant évidement de l'exercice) jusqu'à, au minimum, trouver la valeur de n telle que a^n=1 modulo b puis expliquer pourquoi à partir de ce moment là, c'est les mêmes valeurs qui vont se répéter.

Si ça t'intéresse, je peut te dire que, si tu fait des maths. (ou de l'info.) à un niveau supérieur, tu verra comment calculer ce fameux n tel que a^n=1 modulo b un peu plus simplement qu'en faisant des essais successifs, mais c'est, et de très loin, au dessus du niveau Lycée (au niveau Lycée, en forçant un peu, on pourrait éventuellement montrer qu'un tel n n'existe que si a et b sont premier entre eux et éventuellement montrer que, si p est un nombre premier et que a n'est pas divisible par p alors a^(p-1)=1 modulo p, mais c'est déjà pas évident...)

[Piwatte]

C'est déjà beaucoup plus clair pour moi

Pour la présentation au DS, je demanderai à mon professeur de maths je pense
Je suis en première année en DUT info, j'ai envie de faire des études donc c'est assez important que je comprenne les maths par exemple, sauf que j'ai un professeur qui refuse constamment de faire une correction car il veut qu'on trouve de nous même.. , et en maths je galère un peu, tous les chapitres sont nouveau pour moi .. (j'ai fait un BAC STI2D et pas un BAC S)
Et quand on lui demande de l'aide et que l'on comprend pas du premier coup, il s'en va, nous laissant perdu sans autre explication .. Je vais galérer pendant deux années je le sens haha !

Il me reste à comprendre comment je dois déterminer que N ≡ 6-2+5-3+1-8 (modulo 11) avec N = 813 526
C'est surtout le terme "déterminer" qui me bloque .

[Ben314]

Concernant l'info, je sais pas si votre prof vous en a parlé, mais c'est extrêmement important cette notion de "modulo" et de a^n=1 modulo b vu que c'est la base du système de chiffrement RSA (<- lien) qui est utilisé pour crypter quasiment toutes les informations "plus ou moins sensibles" qui circulent sur le net.

Sinon, concernant les problèmes d'études, y'a le forum, bien sûr, mais aussi les copains : c'est souvent pas mal de travailler à plusieurs (à condition évidement d'arriver à un peu bosser et pas faire que déconner, ce qui est pas toujours évident...)

Enfin, concernant ton autre exo., bien qu'il semble pas mal différent du premier, le raisonnement est fort semblable.
L'astuce (si on peu dire), c'est de comprendre que lorsque l'on écrit par exemple le nombre N=9 543 872, ça veut en fait dire que et que pour trouver à quoi est congru N modulo 11, ça serait pas con de commencer par regarder ce que ça donne 10^0, 10^1, 10^2, 10^3, etc. modulo 11.

[Piwatte]

Notre prof est plutôt du genre à circuler entre les rangs et à critiquer ce que l'on fait sans nous aider .. C'est dommage de pas nous partager ce genre d'information intéressante !

10^0 = 1
10^1 = 10
10^2 = 100 (il reste 1, 11*9 = 99)
10^3=1 000 (il reste 10, 99*10 =990)

On a donc la même chose encore une nouvelle fois

[Ben314]

Oui, exactement (et c'est pas trop fun au niveau variété des exos : ça aurait été mieux que ce soit pas n=2 dans les deux cas le plus petit n tel que a^n=1 modulo b).
Est ce que tu voit le lien avec ton énoncé (y'a plus qu'un mini truc à constater pour terminer)

Sinon, la façon dont tu t'y est pris les deux fois pour calculer les modulo est pas la plus maline : si par exemple on te demande les puissances de 7 modulo 11, tu part évidement de 7^0=1 puis de 7^1=7 puis de 7^2=49=44+5=5 modulo 11.
Mais ensuite, plutôt que de calculer 7^3=49.7=343 puis d'ensuite chercher le reste de la division de 343 par 11, ça va nettement plus vite de partir de 7^3=7².7=5.7=35 modulo 11 (vu que 7²=5 modulo 11).
En particulier, ça t'évite d'avoir de très grand nombre que parfois la calculette ne sait pas manipuler (elle les arrondi) et si les deux nombres a et b (du a^n=1 modulo b) ne sont pas grand, on arrive facilement à tout faire de tête.

[Piwatte]

Non désolé j'arrive pas à voir le lien, le reste est évidemment de 10 (dans mon exercice)

Dans mon exo j'ai 813 526, donc :

pour 8 x 10^6 modulo 11, le reste est de 8
pour 1 x 10^5 modulo 11, le reste est de 1
pour 3 x 10^4 modulo 11, le reste est de 3
etc

Je vois pas pourquoi on alterne entre addition et soustraction

[Ben314]

Tout simplement parce que 10 modulo 11, c'est la même chose que <biiiiiip> modulo 11.

Et les chiffres 8 , 1 et 3 que tu as pris, c'est pas bon vu que c'est une fois sur deux que 10^n=1 modulo 11.
Donc c'est les chiffres 1 , 5 et 6 de 813526 qui correspondent à des puissances de 10 égales à 1 modulo 11.
Et les 3 autres chiffres 8 , 3 et 2 de 813526 eux, il correspondent à des puissances de 10 congrues à 10 donc à <biiiiiip> modulo 11.

[Piwatte]

Donc 2x10^1 modulo 11 => 2 x 1 modulo 11 (car 10^1 =1 modulo 11) ?

Les trois autres chiffres (8,3,2) correspondent donc à des puissances de 10 congrus à 10 donc à -1 modulo 11 ?

A ce niveau là j'arrive à comprendre, c'est au niveau des soustractions et additions que je bloque toujours ..

Je pense que je vais aller dormir et reprendre ça demain avec plus d'énergie !
Je te remercie en tout cas pour l'aide que tu m'as donné, je vais pas dire que je comprends tout, mais j'ai moins de difficulté déjà

Bonne soirée !

[Ben314]

Donc 2x10^1 modulo 11 => 2 x 1 modulo 11 (car 10^1 =1 modulo 11) ?

Oui, modulo que ce ne sont pas du tout des implications mais des "égalités modulo 11" (je pense que tu doit écrire ça comme un égal mais avec 3 traits au lieu de 2)

Et sinon, LA astuce, c'est que, modulo 11, ben 10 c'est la même chose que -1.
Donc par exemple 10^5 c'est égal à -1 modulo 11 et qu'en conséquent, 8.10^5, c'est égal modulo 11 à 8.(-1), c'est à dire à -8.