Raisonnement et démonstration pour les congruences [spé]

[Rebelle_]

Hello tout le monde ! =)

J'ai une petite question de vérification à vous soumettre. Je ne suis pas très sûre de ma démarche dans l'exercice suivant. :/

On demande de déterminer le reste de la division de 2917^(541) par 5.

NB : dans tout l'exercice, [=] signifie "congru à" et (n) est le module n.

On remarque que 2917 [=] 2 (5) <=> 2917^(541) [=] 2^(541) (5)

(question subsidiaire : ma prof affirme que je n'ai pas le droit d'utiliser les équivalences, mais il me semble avoir lu quelque part que la relation de congruence étant réflexive, symétrique et transitive dans Z, ceci fait d'elle une relation d'équivalence dans Z ? Qu'en est-il ?)

De plus :
2 [=] 2 (5)
2² [=] 4 (5)
2^3 [=] 8 (5) donc 2^3 [=] 3 (5)
2^4 [=] 6 (5) donc 2^4 [=] 1 (5)

Or, 541 = 4*135 + 1, donc 2^(541) [=] 2^(4*135 + 1) (5)
<=> 2^(541) [=] (2^4)^(135) * 2 (5)
<=> 2^(541) [=] 2 (5)

Par symétrie, 2917^(541) [=] 2 (5). Le seul reste possible est 2.

[Mortelune]

Bonjour.

Le raisonnement est le bon si j'ai pas lu de travers à part peut être le par symétrie à la fin pas très clair. Après par rapport au raisonnement par équivalence il est sans doute considéré comme peu pédagogique pour la compréhension alors les profs que j'ai pu avoir préféraient la double implication mais dans ce que tu as écrit les implications dans les 2 sens sont vraies donc il y a bien équivalence.

[diditcho]

bonjour je bloque sur exo de math pour demain LE VOICI : f est la fonction définie sur R par : f(x) = x²+x-2
et C est sa courbe représentative
1) Le POINT A (1/2 ; -5/-4 ) est il un point de C
2) La courbe C coupe t'elle l'axe des abscisses au point d'abscisse 1 ? merci de votre aide

[Mortelune]

Crée un nouveau sujet ;)

[Rebelle_]

D'accord merci beaucoup =)

Dans le cours on a appelé "symétrie" la propriété suivante : si a [=] b (n) et b [=] c (n) alors a [=] c (n), avec (a, b, c) des entiers relatifs et n un entier naturel.

[Mortelune]

Ok j'aurai plus appelé ça transitivité mais bon ^^

[Rebelle_]

Ah, je me suis trompée de nom ? C'est moi qui ai mal recopié le cours au tableau alors ! Je change tout de suite sur mon cahier.

Merci ;)

[Sylviel]

une relation entre deux nombres (=, congru, <, ...) qu'on va noté R (donc aRb plutôt que a=b, ou a- symétrique si aRb <=> bRa
- transitive si aRb et bRc => aRc

juste pour vérifier, est ce que "<" est transitive ? est-elle symétrique ?
et pour "=" ?

[Rebelle_]

La relation d'infériorité stricte n'est pas symétrique mais elle est transitive.
La relation d'égalité est symétrique et transitive.

Juste ?

Merci pour les explications :)

[Rebelle_]

De plus :
2 [=] 2 (5)
2² [=] 4 (5)
2^3 [=] 8 (5) donc 2^3 [=] 3 (5)
2^4 [=] 6 (5) donc 2^4 [=] 1 (5)

J'ai une question ! Je ne vois pas trop à quoi sert cette partie. Est-ce pour déterminer les restes possibles qui sont 1, 2, 3 ou 4 ? Si oui ce n'est pas utile parce que les restes de la division par 5 ne peuvent être autres que 1, 2, 3 ou 4...
C'est ma prof qui rédige comme ça mais je n'ai pas pensé à lui demander pourquoi :/

[Olympus]

Salut !

J'ai une question ! Je ne vois pas trop à quoi sert cette partie. Est-ce pour déterminer les restes possibles qui sont 1, 2, 3 ou 4 ? Si oui ce n'est pas utile parce que les restes de la division par 5 ne peuvent être autres que 1, 2, 3 ou 4...
C'est ma prof qui rédige comme ça mais je n'ai pas pensé à lui demander pourquoi :/

C'est une technique qui consiste à trouver la "période" de ta suite de résidus, t'as 2 -> 4 -> 3 -> 1 -> 2 -> 4 -> 3 -> 1 etc... On recherchera donc la première puissance de 2 différente de 1 dont le résidu modulo 5 est 1 .


Je multiplie par 2 :



Je multiplie encore par 2 :



Encore une fois ...



Et bingo, on a trouvé la période .

Donc .

D'où .

[Rebelle_]

Aaah ! Ok je vois !!
Super, merci beaucoup ;D

[benekire2]

On remarque que 2917 [=] 2 (5) 2917^(541) [=] 2^(541) (5)

(question subsidiaire : ma prof affirme que je n'ai pas le droit d'utiliser les équivalences, mais il me semble avoir lu quelque part que la relation de congruence étant réflexive, symétrique et transitive dans Z, ceci fait d'elle une relation d'équivalence dans Z ? Qu'en est-il ?)

Salut, en effet l'implication directe de ce que tu met est assez évidente. Maintenant l'implication réciproque est tout aussi évidente. Il y a donc équivalence .

Le truc c'est que faut faire attention a ta parenthèse (question subidiaire : .... ) , c'est pas parce que la congruence est une relation d'équivalence que forcément quand tu traaille avec tu as toujours des équivalences :

pour un tout n.

Cela dit l'ipmplication réciproque est totalement fausse. Est-tu sûr d'avoir compris (j'en doute pas ! ) ? Enfin d'avoir compris que ici savoir que c'est une relation d'équivalence ,en soi, ne nous permet pas de justifier ton équivalence entre tes deux propositions ...

[Sylviel]

Au fait oui c'est juste pour les relations ;-)

[Rebelle_]

En fait je pense ne pas avoir compris dans quels cas on a équivalence et dans quels cas on n'a pas équivalence.
Pour la relation que tu cites je vois bien pourquoi, mais dans d'autres je ne suis pas sûre de pouvoir le dire aussi clairement !

[Nightmare]

Rebelle_ > Il n'y a aucun lien, en tout cas pas tel que tu l'entends, entre la notion de relation d'équivalence et le symbole d'équivalence <=> (si ce n'est qu'il se comporte comme une relation d'équivalence).

[Rebelle_]

Ah ? Je n'ai rien compris alors :/
Je pense que je vais m'en tenir aux implications alors, comme ça je ne risque pas de dire des bêtises et même s'il y a équivalence on ne m'en voudra pas de ne pas l'avoir mentionné ^^'

[Sylviel]

Deux choses distinctes :
1) la notion de "relation d'équivalence" ie une relation interne sur un ensemble, symétrique, transitive et reflexive.
Exemple : =, congruence, "triangles semblables"...
2) l'équivalence de deux proposition. une proposition A équivaut à B si
- A => B
- B => A
ou encore A est vraie si B est vraie, et A est faux si B est faux.
c'est le cas par exemple lors de la résolution d'une équation simple :
3x+1=2
<=> 3x=1 (pas la peine d'écrire les deux implications...)

Mais souvent on ne raisonne pas par équivalence car c'est trop compliqué, on préfére agir en 2 temps : A=>B, B=>A.

Je ne sais pas si je suis plus clair ^^'

[Nightmare]

En fait, je ne comprends pas ce que tu ne comprends pas, ou plutôt, je ne comprends pas ce que tu as cru comprendre et ne comprend plus. On a deux notions mathématiques bien distinctes, même si la relation de congruence entre les entiers porte effectivement le nom de "relation d'équivalence", rien ne suggère, dans la définition de cette dernière, de lien avec la notion d'équivalence logique entre deux assertions.

[Rebelle_]

Si si, je pense que ça va :)

Donc pour être rigoureux il faut justifier chaque équivalence quand la justification n'est pas triviale (comme dans le cas de la résolution d'équation du premier degré par exemple). Si oui alors je vois bien la difficulté de la chose :) L'utilisation des implications est de fait plus simple parce qu'elle suppose de démontrer la relation dans un sens, alors que l'équivalence est une double-implication, c'est-à-dire deux choses différentes à démontrer.
On doit pouvoir remonter le raisonnement par équivalences en même temps qu'on le descend, alors que le raisonnement par implications ne fait que "couler" sans remonter. Ce sont mes petites images pour comprendre ^^'