Congruences : reste division euclidienne

Aide à la résolution d'exercices ou de problèmes de niveau Lycée.

Modérateur: gdm_aidesco

Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Ne poster qu'un exercice (ou problème) par sujet et indiquer son niveau précis dans le titre du message.

Congruences : reste division euclidienne

Messagepar g_D » Lundi 19 Novembre 2012, 20:06

Bonjour, j'ai un exercice en spé maths que je ne comprends pas. Malheureusement, je n'ai pas les étapes intermédiaires, mon prof a rédigé l'exercice comme ça. Je ne comprends pas comment il fait et pourquoi le modulo 5 devient à un moement modulo 4. Pourriez-vous m'aider ?
Merci d'avance pour vos explications.

Quel est le reste de la division euclidienne de 12^1527 par 5 ?

12 congru à 2 [5]
Don 12^1527 congru à 2^1527 [5]
Or 1527 congru à 3 [4]
Donc on a 2^1527 congru à 3 [5]
Et par suite, 12^1527 congru à 3 [5]
g_D
Déca-utilisateur
 
Messages: 16
Inscription: Jeudi 08 Novembre 2012, 10:23
Statut actuel: Lycée | Terminale S

Publicité

Re: Congruences : reste division euclidienne

Messagepar nicolas reitmeier » Mardi 20 Novembre 2012, 08:12

g_D a écrit:Bonjour, j'ai un exercice en spé maths que je ne comprends pas. Malheureusement, je n'ai pas les étapes intermédiaires, mon prof a rédigé l'exercice comme ça. Je ne comprends pas comment il fait et pourquoi le modulo 5 devient à un moement modulo 4. Pourriez-vous m'aider ?
Merci d'avance pour vos explications.

Quel est le reste de la division euclidienne de 12^1527 par 5 ?

12 congru à 2 [5]
Don 12^1527 congru à 2^1527 [5]
Or 1527 congru à 3 [4]
Donc on a 2^1527 congru à 3 [5]
Et par suite, 12^1527 congru à 3 [5]


$1527=4\times381+3$

Donc :

$1527\equiv 3\left [ 4 \right ]$

Or,

$12^{1527}=(12^4)^{381}\times12^3$

A quoi sont congrus $12^4$ et $12^3$ modulo 5 ?
Donc qu'en est-il de $12^{1527}=(12^4)^{381}\times12^3$ ?

Il faut forcer c'est dur au début. Faites beaucoup d’exercices.
nicolas reitmeier
Déca-utilisateur
 
Messages: 25
Inscription: Lundi 08 Octobre 2012, 21:34
Statut actuel: Collège

Re: Congruences : reste division euclidienne

Messagepar g_D » Mardi 20 Novembre 2012, 08:52

$12^{4}$ congru à 1 modulo 5 et $12^{3}$ congru à 3 modulo 5.
Donc $12^{1527}$ congru à 3 modulo 5.

Je pense comprendre la fin, le problème c'est pourquoi un modulo 4 ? Pourquoi est-ce qu'on ne fait pas $1527=5 \times 305+2$ ?
Dernière édition par rebouxo le Mardi 20 Novembre 2012, 11:08, édité 1 fois.
Raison: Pour le signe multiplier, il faut utiliser \times ;-)
g_D
Déca-utilisateur
 
Messages: 16
Inscription: Jeudi 08 Novembre 2012, 10:23
Statut actuel: Lycée | Terminale S

Re: Congruences : reste division euclidienne

Messagepar rebouxo » Mardi 20 Novembre 2012, 11:09

Ben qu'est-ce que cela donne si tu utilises cette décomposition de $1527$ ?

Olivier
A line is a point that went for a walk. Paul Klee
Par solidarité, pas de MP
rebouxo
Modérateur
 
Messages: 6909
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Re: Congruences : reste division euclidienne

Messagepar g_D » Mardi 20 Novembre 2012, 11:59

Ca ferait $12^{1527}$ congru à 0 modulo 5 ?
g_D
Déca-utilisateur
 
Messages: 16
Inscription: Jeudi 08 Novembre 2012, 10:23
Statut actuel: Lycée | Terminale S

Re: Congruences : reste division euclidienne

Messagepar balf » Mardi 20 Novembre 2012, 16:09

On utilise petit Fermat, puisque 5 est premier.

B.A.
balf
Zetta-utilisateur
 
Messages: 3811
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Congruences : reste division euclidienne

Messagepar rebouxo » Mardi 20 Novembre 2012, 17:31

balf a écrit:On utilise petit Fermat, puisque 5 est premier.

B.A.


Ca, c'est un message qui risque d'être un peu crypté. Je ne suis pas sur que le petit théorème de Fermat soit au programme de spé math. Mais la question c'est bien pourquoi on utilise 4 et pas 5 ?

Olivier
A line is a point that went for a walk. Paul Klee
Par solidarité, pas de MP
rebouxo
Modérateur
 
Messages: 6909
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Re: Congruences : reste division euclidienne

Messagepar g_D » Mardi 20 Novembre 2012, 19:44

Oui, la question est bien ça. Et on n'a pas vu le petit Fermat.
g_D
Déca-utilisateur
 
Messages: 16
Inscription: Jeudi 08 Novembre 2012, 10:23
Statut actuel: Lycée | Terminale S

Re: Congruences : reste division euclidienne

Messagepar balf » Mardi 20 Novembre 2012, 20:34

Le nœud de l'argumentation est que, si a n'est pas congru à 0 mod. 5, a$^{\mathsf 4}$ est congru à 1 mod.5 (petit théorème de Fermat).
Naturellement, ceci peut se vérifier pour a = 12 à la main : comme 12 $\equiv $ 2, 12$^{\mathsf 4} \equiv $ 2$^{\mathsf 4}$ = 16 $\equiv $ 1 (mod. 5). Donc, aussi, 12$^{\mathsf{4k}} \equiv $ 1$^{\mathsf k} \equiv $ 1 (mod. 5), et en particulier 12$^{\mathsf{1524}} \equiv $ 1 (mod. 5).

B.A.
balf
Zetta-utilisateur
 
Messages: 3811
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Congruences : reste division euclidienne

Messagepar rebouxo » Mardi 20 Novembre 2012, 20:39

g_D a écrit:Oui, la question est bien ça. Et on n'a pas vu le petit Fermat.


Le petit Fermat est attendu par ses parents à l'accueil de mathematex. Le petit Fermat :mrgreen:

Désolé, j'ai pas pu me retenir.


Bon, cela dit, cela donne quoi avec ta décomposition (sachant que ce que tu as écris est faux).
Olivier
A line is a point that went for a walk. Paul Klee
Par solidarité, pas de MP
rebouxo
Modérateur
 
Messages: 6909
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Re: Congruences : reste division euclidienne

Messagepar g_D » Mardi 20 Novembre 2012, 21:32

D'accord, je crois que c'est compris.
Au fait, Olivier, bien vu pour le petit Fermat^ :lol:
Merci à vous.
g_D
Déca-utilisateur
 
Messages: 16
Inscription: Jeudi 08 Novembre 2012, 10:23
Statut actuel: Lycée | Terminale S

Re: Congruences : reste division euclidienne

Messagepar balf » Mardi 20 Novembre 2012, 23:04

@ Olivier : en fait la rédaction du prof utilisait Fermat, dans le message initial,manifestement. Maintenant, je ne sais pas s'il a été vu officiellement ou si tel ou tel enseignant l'a fait sous forme de TD. S'il n' a pas été vu, la rédaction proposée est pour le moins elliptique…

@ g_D : il y a une partie du corrigé retranscrite de façon erronée :
Or 1527 congru à 3 [4]
Donc on a 2^1527 congru à 3 [5]

La conclusion est en réalité : donc on a 2^1527 congru à 2^3 = 8 [5]

B.A.
balf
Zetta-utilisateur
 
Messages: 3811
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Congruences : reste division euclidienne

Messagepar rebouxo » Mardi 20 Novembre 2012, 23:29

Ben j'avions perdu le petit Fermat. Il faut dire qu'il est bien remuant, et qu'il n'arrête pas de se perdre (en particuliers dans les marges).

Olivier
A line is a point that went for a walk. Paul Klee
Par solidarité, pas de MP
rebouxo
Modérateur
 
Messages: 6909
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Re: Congruences : reste division euclidienne

Messagepar balf » Mardi 20 Novembre 2012, 23:56

:lol:

B.A.
balf
Zetta-utilisateur
 
Messages: 3811
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence


Retourner vers Exercices et problèmes : Lycée

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 5 invités