Cryptage

**mehdi_128** · 30/10/2018, 15h26

Bonjour,

Je suis bloqué depuis 2 jours sur cette question. Si quelqu'un pourrait m'aider ça serait sympa

Soit $\text{[math]}$ . Soit $\text{[math]}$ .

Pour tout entier naturel $\text{[math]}$ non nul, on note $\text{[math]}$ l'application de $\text{[math]}$ dans $\text{[math]}$ qui à tout $\text{[math]}$ de $\text{[math]}$ associe le reste de la division euclidienne de $\text{[math]}$ par $\text{[math]}$ .

On a montré les résultats suivants :

1) $\text{[math]}$

2) Soient $\text{[math]}$ et $\text{[math]}$ les uniques éléments de $\text{[math]}$ tels que : $\text{[math]}$ et $\text{[math]}$ :

$\text{[math]}$ divise $\text{[math]}$

3) Si $\text{[math]}$ et $\text{[math]}$ sont premiers entre eux alors $\text{[math]}$ est bijective.

Je ne comprends pas comment obtenir le résultat suivant :

Si 28 et $\text{[math]}$ ne sont pas premiers entre eux, il n'existe aucun $\text{[math]}$ tel que : $\text{[math]}$ pour $\text{[math]}$ alors $\text{[math]}$ n'est pas surjective.

invite23cdddab · 30/10/2018, 15h46

Si $\text{[math]}$ , alors $\text{[math]}$

Donc d'après 2), 28 divise kt-1

Maintenant, soit m le pgcd de 28 et de k, est-ce que m divise kt-1 ? Conclusion?

**mehdi_128** · 30/10/2018, 16h35

Je suis d'accord jusqu'ici :

$\text{[math]}$

Après j'ai pas compris, on a pas la valeur de $\text{[math]}$ comment faire ?

Si $\text{[math]}$ donc $\text{[math]}$ et $\text{[math]}$ et $\text{[math]}$ car 28 et k non premiers entre eux.

Donc $\text{[math]}$

Mais je sais pas si $\text{[math]}$ divise $\text{[math]}$

**mehdi_128** · 30/10/2018, 16h51

J'ai pas compris pourquoi on passe par le PGCD ici.

A voir en vidéo sur Futura · Aujourd'hui

invite23cdddab · 30/10/2018, 18h14

Tu ne vois vraiment pas le lien entre "k et 28 pas premiers entre eux" et le PGCD de 28 et k?

Et sinon, savoir pourquoi m ne divise pas kt-1, c'est vraiment la base de la base. Mais soit, imaginons que tu ne sache plus rien du tout. Si m divise kt et m divise kt-1, qu'est-ce que tu peux en déduire?

**mehdi_128** · 30/10/2018, 20h19

Alors si 28 et k sont pas premiers entre eux : $\text{[math]}$

Si ( $\text{[math]}$ et $\text{[math]}$ ) (1) alors $\text{[math]}$ car m divise n'importe quelle combinaison linéaire de $\text{[math]}$ et $\text{[math]}$

D'où $\text{[math]}$ ce qui est impossible car $\text{[math]}$ d'où une contradiction.

Donc par négation de (1) ( $\text{[math]}$ ne divise pas $\text{[math]}$ ou $\text{[math]}$ ne divise pas $\text{[math]}$ ) alors forcément $\text{[math]}$ ne divise pas $\text{[math]}$

On a montré que le $\text{[math]}$ ne divise pas $\text{[math]}$

Je vois pas quoi faire après avoir montré que ça

**mehdi_128** · 30/10/2018, 22h32

Je n'arrive pas à montrer que :

$\text{[math]}$ ne divise pas $\text{[math]}$ $\text{[math]}$ 28 ne divise pas $\text{[math]}$

invite51d17075 · 30/10/2018, 23h25

Envoyé par mehdi_128

Je n'arrive pas à montrer que :

$\text{[math]}$ ne divise pas $\text{[math]}$ $\text{[math]}$ 28 ne divise pas $\text{[math]}$

je n'ai même pas lu le fil, mais il semble évident que si 28 divise kt-1 alors tous les diviseurs de 28 divisent kt-1
Or, m est diviseur de 28 et ne divise pas kt-1 , donc un multiple de m ( 28 ici ) ne peut diviser kt-1.

**mehdi_128** · 31/10/2018, 00h01

Ansset

AH ouai c'est compliqué on fait encore une contraposée pour montrer déjà une contraposée, je m’emmêle les pinceaux. Y a pas plus simple ?

invite51d17075 · 31/10/2018, 00h07

ben tu le formule comme tu veux , mais on ne démontre pas une contraposée, mais l'implication par contraposée.

invite51d17075 · 31/10/2018, 00h18

Non en fait, c'est mal dit et même faux de ma part ( post #8 ) désolé, mais il est tard.

invite51d17075 · 31/10/2018, 00h28

je tombe de sommeil et raconte du nawak, il vaut mieux que te souhaite une bonne nuit.
Cdt

**mehdi_128** · 31/10/2018, 00h30

Pas de problème Ansset, bonne nuit.

J'attendrai la réponse de Tryss.

**mehdi_128** · 02/11/2018, 06h05

J'ai trouvé la solution d'une autre manière.

Si $\text{[math]}$ alors $\text{[math]}$ on a $\text{[math]}$ .

Ce qui peut s'écrire $\text{[math]}$ où $\text{[math]}$ est un entier.

C'est à dire la relation de Bézout montrant que k et 28 sont premiers entre eux.

Donc par contraposée on a pour $\text{[math]}$ fixé dans $\text{[math]}$ tel que $\text{[math]}$

k et 28 pas premiers entre eux $\text{[math]}$ NON( $\text{[math]}$ )

Ce qui donne : k et 28 pas premiers entre eux $\text{[math]}$ $\text{[math]}$

Il n'existe aucun $\text{[math]}$ tel que $\text{[math]}$

Cryptage

Cryptage

Re : Cryptage

Re : Cryptage

Re : Cryptage

Re : Cryptage

Re : Cryptage

Re : Cryptage

Re : Cryptage

Re : Cryptage

Re : Cryptage

Re : Cryptage

Re : Cryptage

Re : Cryptage

Re : Cryptage

Discussions similaires

Cryptage RSA

cryptage

Cryptage

Cryptage RSA

Cryptage