Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Reprise d'études [tout]Lister tous les topics de mathématiques

1 2 +

Niveau Reprise d'études
Partager :

Congruence

Posté par Profil Ramanujan 24-10-18 à 04:29

Bonsoir,

Je vais sûrement poser une question bête mais n'ayant pas touché d'arithmétique depuis des lustres, mon niveau est au raz des pâquerettes.

Soit i un entier non nul et k,l des entiers des entiers naturels non nuls.

J'ai : i ^k \equiv i^l [29]

Je veux montrer que la division euclidienne de i ^k et i ^l par 29 donne un reste identique.

Posté par
lionel52re : Congruence 24-10-18 à 08:57

Salut

Pourquoi tu écris jamais lenoncé complet?
Pourquoi quand tu ecris ton propre énoncé tu vérifies pas que tu écris nimp ca prend 2 secondes...

Allo tu as le Capes à passer à un moment va falloir apprendre à etre plus rigoureux que ça


Prends i = 2 k =1 et l = 2

Posté par
Sylvieg Moderateurre : Congruence 24-10-18 à 08:57

Bonjour,
De manière plus générale, que signifie a b [29] ?
Le fait que a et b soient ou non de la forme ip n'intervient pas.

Posté par
lakere : Congruence 24-10-18 à 08:57

Bonjour,

Quelle est la définition de:

  a\equiv b\;\;[p] ?

Posté par
lakere : Congruence 24-10-18 à 08:58

Bonjour Sylvieg

Posté par
lionel52re : Congruence 24-10-18 à 09:00

Et oups sorry jai mal lu lénoncé MAIS donc oublie mon message désolé...

Mais là tu viens décrire la définition de la congruence
La définition de
A congru à B modulo C

C'est A et B ont meme reste dans la div euclidienne par C

Posté par
Sylvieg Moderateurre : Congruence 24-10-18 à 09:01

Bonjour lionel52,
Quelle est la probabilité qu'un message posté à 4h29 reçoive deux premières réponses simultanées après 8h ?
Sinon, je ne vois pas l'intérêt de ton exemple

Posté par
Sylvieg Moderateurre : Congruence 24-10-18 à 09:06

Bonjour lake
Je modifie :
Quelle est la probabilité qu'un message posté à 4h29 reçoive deux trois premières réponses simultanées après 8h ?

Posté par
lakere : Congruence 24-10-18 à 09:07

Posté par Profil Ramanujanre : Congruence 24-10-18 à 10:39


Que p / (a-b) donc qu'il existe un entier relatif k tel que :

a-b = k p

Posté par
Sylvieg Moderateurre : Congruence 24-10-18 à 10:41

C'est aussi équivalent à a et b ont le même reste dans la division euclidienne par p .
Comme écrit par lionel52 .

Posté par
lionel52re : Congruence 24-10-18 à 13:04

Si a-b est divisible par k on peut ecrire

a - b = kq

Donc a = kq + b = kq + kq' + r
Où r est le reste de la division euclidienne de b par k!

Posté par Profil Ramanujanre : Congruence 24-10-18 à 15:07

lionel52 @ 24-10-2018 à 13:04

Si a-b est divisible par k on peut ecrire

a - b = kq

Donc a = kq + b = kq + kq' + r
Où r est le reste de la division euclidienne de b par k!


J'ai pas compris Il sort d'où ce q' ?

Posté par Profil Ramanujanre : Congruence 24-10-18 à 15:10

\exists k \in \Z : a-b = k p

Après je vois pas pour montrer que a et b divisés par p  donnent le même reste.

Posté par
Sylvieg Moderateurre : Congruence 24-10-18 à 17:48

Je complète le message de lionel52 :
Si a-b est divisible par k on peut écrire

a - b = kq

Donc a = kq + b = kq + kq' + r
Où r est le reste de la division euclidienne de b par k
c'est à dire b = kq'+r avec 0r

Posté par Profil Ramanujanre : Congruence 24-10-18 à 17:53

a = kq + b je suis d'accord.

Mais après je comprends rien c'est quoi ce q' sorti du chapeau ?

Et ça sort d'où ce : 0 \leq r < k ? Vous l'avez démontré où ?

Posté par
Sylvieg Moderateurre : Congruence 24-10-18 à 17:55

Tu traduis comment "r est le reste de la division euclidienne de b par k" ?

Posté par
matheuxmatoure : Congruence 24-10-18 à 17:59

bonsoir... encore en train de mouliner la-dessus ?

autre façon de voir (en fait c'est la même ) :

pour un entier "a" donné, l'ensemble des entiers congrus à "a" modulo 29 est une classe d'équivalence de la relation "... est congru à ... modulo 29"

le reste d'un entier "a" dans sa division par 29 est le plus petit entier positif ou nul de sa classe d'équivalence

si a et b sont congrus modulo 29, ils ont la même classe d'équivalence, donc le même reste dans la division par 29

et pis c'est tout !

Posté par Profil Ramanujanre : Congruence 24-10-18 à 18:02

\exists q \in \Z : b=kq +r avec 0 \leq r < b

Posté par Profil Ramanujanre : Congruence 24-10-18 à 18:04

matheuxmatou @ 24-10-2018 à 17:59

bonsoir... encore en train de mouliner la-dessus ?

autre façon de voir (en fait c'est la même ) :

pour un entier "a" donné, l'ensemble des entiers congrus à "a" modulo 29 est une classe d'équivalence de la relation "... est congru à ... modulo 29"

le reste d'un entier "a" dans sa division par 29 est le plus petit entier positif ou nul de sa classe d'équivalence

si a et b sont congrus modulo 29, ils ont la même classe d'équivalence, donc le même reste dans la division par 29

et pis c'est tout !


Classe d'équivalence donc forcément symétrique !

Mais j'aimerais savoir le démontrer sans utiliser les classes d'équivalence.
Il faut savoir l'expliquer à une classe de terminale.

Posté par
matheuxmatoure : Congruence 24-10-18 à 18:10

Ramanujan @ 24-10-2018 à 18:02

\exists q \in \Z : b=kq +r avec 0 \leq r < b


alors essaye de lire scrupuleusement toutes les réponses qui t'ont été données !

et comme on ne sait rien de ton niveau , j'en arrive à supposer que c'est bac + 37

quant ce que tu écris c'est loufoque ... la contrainte sur le reste est fausse ... en plus on divise par 29 donc je ne vois pas qui est k ici

Posté par Profil Ramanujanre : Congruence 24-10-18 à 18:20

Matheux

J'ai fait MPSI/MP puis école d'ingé y a plus de 5 ans et je reprends les maths en étudiant seul. J'attends de recevoir un livre sérieux de cours MPSI et en attendant je fais les épreuves de CAPES de maths 2018. J'ai fini l'épreuve 1 et là je suis sur l'épreuve 2.

Je comprends rien à leur réponse ils introduisent un q' qui vient de nulle part sans le définir.

Bref, j'avais a \equiv b [29] équivalent à

a - b  = 29k où k \in \Z

Et après je vois pas.

Posté par
matheuxmatoure : Congruence 24-10-18 à 18:23

d'accord, ben mets le dans ton profil

je résume :

il existe un entier k tel que a = b + 29k

la division de b par 29 est b=29q + r avec q , r entiers et 0r<29

remplace

donc a = 29(k+q) + r

donc a et b ont le même reste dans la division euclidienne par 29

Posté par Profil Ramanujanre : Congruence 24-10-18 à 18:42

Merci Matheux c'était simple en fait

Le q' en fait c'était : q' = k + q \in \Z car la somme de 2 entiers relatifs est un entier relatif.

Mais j'étudierai aussi avec les classes d'équivalence c'est important quand on étudie \Z / n \Z

Posté par
matheuxmatoure : Congruence 24-10-18 à 18:44

pas de quoi

mm

Posté par Profil RamanujanPartie non vide 24-10-18 à 19:03

Bonsoir,

Dans un problème j'ai un ensemble et j'ai démontré qu'il est non vide. J'aimerais démontrer qu'il admet un plus petit élément.

Mais c'est une partie de \N^*

Et le théorème est : toute partie non vide de \N admet un plus petit élément.

Comment faire ?

*** message déplacé ***

Posté par
jsvdbre : Partie non vide 24-10-18 à 19:06

Bonjour Ramanujan.
toute partie non vide de \N^* est une partie non vide de \N, donc admet un plus petit élément.

*** message déplacé ***

Posté par Profil Ramanujanre : Partie non vide 24-10-18 à 20:34

Salut Jsvdb

Merci j'ai compris. Je bloque sur la suite.

Soit x un nombre entier premier avec 29

1/ Montrer qu'il existe un plus petit entier naturel non nul k tel que x^k \equiv 1 [29] et que cet entier est inférieur ou égal à 28. Cet entier s'appelle l'ordre de x et on le note o(x).

J'ai fait : soit E = \{ k \in \N^* , x^k \equiv 1 [29] \}

E est une partie de \N^* \subset \N et non vide car 28 \in E d'après le petit théorème de Fermat.
E admet un plus petit élément qui vérifie :

1 \leq o(x) \leq 28

2/ Soit k un entier naturel. Montrer que :

x^k \equiv 1 [29] \Leftrightarrow o(x) / k

Je me demande s'il y a pas une coquille dans la question j'aurais pris k dans \N^* et pas \N...

Montrons <=

Si o(x) / k alors il existe q \in \N tel que :

k = o(x) \times q

Alors x^k = x^{o(x)q} = (x^{o(x})^q

Or : x^{o(x)} \equiv 1 [29] donc par stabilité des congruences par produit :

x^{o(x)q} = x^k \equiv 1 [29]

Pour l'autre implication j'ai pas réussi : =>

*** message déplacé ***

Posté par
lionel52re : Congruence 24-10-18 à 21:08

Oui k est un entier non nul !

Pour l'implication réciproque, c'est beaucoup plus compliqué (mais c'est une démonstration classique), je te conseille de prendre k et de faire la division euclidienne de k par o(x) et de voir ce que ça peut donner

Posté par
matheuxmatoure : Congruence 24-10-18 à 21:16

lionel52 il est banni ... n'insiste pas !

Posté par
lionel52re : Congruence 24-10-18 à 21:26

...ce qui est idiot il faisait de mal à personne

Posté par
matheuxmatoure : Congruence 24-10-18 à 21:26

(ben je sais pas pourquoi, je viens juste de le remarquer... multipost répété peut-être)

Posté par
lionel52re : Congruence 24-10-18 à 21:28

Ce forum d'après moi a toujours eu des règles à la soviétique...

Posté par Profil Ramanujanre : Congruence 27-10-18 à 16:42

Bonjour, j'ai purgé ma peine

Voilà, j'ai résolu cette question mais je bloque sur une question dans la suite.

On a montré que x^k \equiv 1 [29] \Leftrightarrow o(x) / k

Soit z \in [|1,28|] et t l'unique élément de [|1,28|] tel que z \equiv 2^t [29].
Soit y \in [|1,28|] et x l'unique élément de [|1,28|] tel que y \equiv 2^x [29].

Démontrer que : z^k \equiv y [29] \Leftrightarrow 28 / (kt -x)

Je pensais à faire : z \equiv 2^t [29] \Rightarrow z^k \equiv 2^{tk} [29] \Rightarrow 2^{tk} \equiv z^k [29].

Comme : y \equiv 2^x [29]

z^k \equiv y [29] \Rightarrow z^k \equiv 2^x [29] \Rightarrow 2^{tk} \equiv 2^x [29]

Mais mon problème est que je n'ai pas gardé l'équivalence, comment faire ?

Je suis obligé de travaillé par implication ici car j'utilise le produit de congruence et la transitivité

Posté par
carpediemre : Congruence 27-10-18 à 17:26

salut

Ramanujan @ 24-10-2018 à 18:20

J'ai fait MPSI/MP puis école d'ingé y a plus de 5 ans ben va bosser ...

et je reprends les maths en étudiant seul. J'attends de recevoir un livre sérieux de cours MPSI il n'y a pas besoin de livre de math sérieux il est besoin de penser et réfléchir sérieusement ...

et en attendant je fais les épreuves de CAPES de maths 2018.  je plains tes futurs éllèves ...

J'ai fini l'épreuve 1 que j'aimerais voir ...

et là je suis sur l'épreuve 2.

Je comprends rien à leur réponse ils introduisent un q' qui vient de nulle part sans le définir.  ça m'étonnerait ...

Bref, j'avais a \equiv b [29] équivalent à

a - b  = 29k où k \in \Z

Et après je vois pas.


si a = 29p + r est UNE division de a par 29 alors pour tout entier k        a + 29k = 29(p + k) + r

maintenant si on pose b = a + 29k et si \red 0 \le r < 29 alors la celle ci-dessus division de a par b est LA division euclidienne de a par 29 et il en est de même pour b = a + 29k = 29(p + k) + r

c'est tellement élémentaire (niveau collège)

et on a donc a \equiv b  [29]



on veut maintenant montrer que   \forall n \in \N  :  a^n \equiv b^n  [29]

par récurrence il suffit de montrer qu'il suffit de montrer que :

a \equiv b  [29] $ et $ c \equiv d  [29] => ac \equiv bd  [29]

puis qu'il suffit de montrer que   \forall c \in \N  :  a \equiv b  [29] => ac \equiv bc  [29]

puisqu'on a trivialement c \equiv c  [29]

Posté par
verdurinre : Congruence 27-10-18 à 17:28

Bonsoir,
où utilises tu un produit de congruence dans ta suite d'implication ?

Posté par Profil Ramanujanre : Congruence 27-10-18 à 17:31

@Carpediem

J'ai très bien compris.

Posté par Profil Ramanujanre : Congruence 27-10-18 à 17:33

@Carpediem

J'ai très bien compris.

verdurin @ 27-10-2018 à 17:28

Bonsoir,
où utilises tu un produit de congruence dans ta suite d'implication ?


Non en fait je l'utilise pas, j'utilise la transitivité.

Y a t-il équivalence dans la transitivité des congruences ?

a \equiv b [n] et b \equiv c [n] si et seulement si a \equiv c [n] ?

Posté par
verdurinre : Congruence 27-10-18 à 17:56

Citation :
a \equiv b [n] et b \equiv c [n] si et seulement si a \equiv c [n]
est évidement faux.
D'ailleurs ça reste faux si tu remplace les congruences par des égalités.

Mais ton raisonnement n'utilise jamais la formule (a=c)\implies \bigl((a=b)\land(b=c)\bigr).
Même si tu le fais dans le sens réciproque.

Posté par Profil Ramanujanre : Congruence 27-10-18 à 17:59

J'ai réussi à montrer l'implication en utilisant le produit et la transitivité des congruences.

z^k \equiv y [29] \Rightarrow 2^{tk} \equiv 2^x [29]

Mais je vois pas comment travailler par équivalence

Exemple : z \equiv 2^t [29] \Rightarrow z^k \equiv 2^{tk} [29]

Posté par Profil Ramanujanre : Congruence 27-10-18 à 18:04

verdurin @ 27-10-2018 à 17:56

Citation :
a \equiv b [n] et b \equiv c [n] si et seulement si a \equiv c [n]
est évidement faux.
D'ailleurs ça reste faux si tu remplace les congruences par des égalités.

Mais ton raisonnement n'utilise jamais la formule (a=c)\implies \bigl((a=b)\land(b=c)\bigr).
Même si tu le fais dans le sens réciproque.


Je vois mais du coup j'arrive pas à comprendre pourquoi j'ai équivalence dans mes égalités alors que je multiplie et utilise la transitivité plusieurs fois.

Posté par
verdurinre : Congruence 27-10-18 à 19:33

J'écris a\equiv b pour a\equiv b\pmod{29}.

Tu as comme hypothèses :

z\equiv 2^t \text{ et }y\equiv 2^x

Tu veux montrer que, sous ces hypothèses,

z^k \equiv y\iff (kt-x)\,|\,28.

Tu as le droit d'introduire les hypothèses n'importe où dans tes raisonnements.
Ce sont des axiomes.

Posté par Profil Ramanujanre : Congruence 29-10-18 à 00:17

D'accord Verdurin

Je suis arrivé à : 2^{tk} \equiv 2^x [29]

Je comprends pas comment on arrive à : 2^{tk-x} \equiv 1  [29]

Je sais qu'on a pas le droit de diviser les congruences, mais du coup je vois pas comment faire.

Posté par
verdurinre : Congruence 29-10-18 à 06:52

On peut diviser car 29 est premier donc Z/29Z est un corps.

Si cette solution ne te convient pas, tu peux utiliser le petit théorème de Fermat.

Ici il donne  2^{28}\equiv 1 \pmod{29}

Posté par Profil Ramanujanre : Congruence 29-10-18 à 12:05

J'ai compris la méthode avec l'inversibilité de \bar{2} dans \Z/29\Z car 2 et 29 sont premiers entre eux.
Du coup, il faut repasser par les classes : \bar{2}^{tk} = \bar{2}^x

Par contre j'ai pas pas compris la méthode de Fermat

Posté par
lionel52re : Congruence 29-10-18 à 13:40

Hello ! Plus simple (et je pense dans l'esprit de l'énoncé) :

2^{tk} = 2^x [29]
Donc (puisque 28-x \geq 0 donc pas besoin de parler d'inverse)

2^{tk}2^{28-x} = 2^{28} [29]

Soit

2^{tk-x} = 1 [29]

Posté par
lafol Moderateurre : Congruence 29-10-18 à 13:49

Bonjour
lionel, comment "passes"-tu de ta première à ta deuxième ligne, sinon en multipliant par un inverse ?

Posté par Profil Ramanujanre : Congruence 29-10-18 à 14:06

@Lionel

Bien vu

@Lafol

Il a juste multiplié par 2^{28-x} les congruences pas besoin d'inverse.

Posté par
lafol Moderateurre : Congruence 29-10-18 à 14:07

en effet, j'ai lu trop vite

Posté par Profil Ramanujanre : Congruence 29-10-18 à 14:11

Je mets la suite du problème, je bloque sur une question.

On considère l'équation diophantienne où les inconnues sont a et b des entiers relatifs. Soit k,t \in [|1,28|].

ak + 28b =1

1/ Donner une condition nécessaire et suffisante pour que cette équation admette des solutions.
k et 28 premiers entre eux.

2/ On suppose cette condition satisfaite. A partir d'une solution particulière (a_0,b_0) donner alors toutes les solutions.

Je trouve : a=a_0 + 28p et b=b_0 - kp avec p \in \mathbb{Z}

3/ On suppose cette condition satisfaite. Etablir que l'équation a une unique solution (a_1,b_1) pour laquelle a_1 \in [|1,28|]

Je ne vois pas du tout comment faire pour cette question.

1 2 +


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !