Bonjour à tous
J'ai un devoir maison à faire et j'ai du mal avec certaines questions, donc j'ai besoin de votre aide.
Voici l'énoncé :

Tout d'abord pour le 2/f, j'ai deux hésitations :
- à la question c), j'ai trouvé comme valeurs : 1, an, bn et 25. Elles sont correctes ? Si oui, il y en a-t-il d'autres ?
- à la question f), j'ai dit que dn = 25 si et seulement si n = 18 (mod 25). Par contre au niveau de la démonstration, j'ai l'impression d'un peu tourner en rond : pour le premier sens : je suis parti de dn = 25, et je tombe sur n = 18 (mod 25). Puis pour le deuxième sens, je suis parti de n = 18 (mod 25), mais j'ai l'impression que je me mords un peu la queue dans le raisonnement : je pars d'une valeur que j'ai trouvée précédemment, pour montrer le postulat sur lequel je suis parti dans le premier sens, ça ne me paraît pas très correct

Ensuite, pour le 2/N, je bloque dès la question b) de la Partie A : je ne vois pas comment montrer que a est premier avec b², que ce soit en partant d'une égalité de Bezout, ou de la définition du PGCD...

Merci à vous

Personne ?

C'est toi qui avais posté le truc avec le chiffrement RSA?

Exact, pourquoi ?

d_n = pgcd(a_n,25), donc d_n divise 25. Les valeurs possibles de d_n sont 1, 5 et 25.

Si d_n = 25, alors 25 divise a_n = n + 7. Donc n + 7 = 0[25] donc n = - 7 = 18[25].
Réciproquement si n = 18[25], 25 divise a_n, et donc 25 divise d_n (les diviseurs communs sont les diviseurs du pgcd). Mais comme d_n vaut au maximum 25, d_n = 25.

Si d = pgcd(a,b²), d divise a et d divise b², donc d divise bua + vb² = b. Ainsi d divise a et d divise b. Comme a et b sont premiers entre eux, d = 1.

Salut Prauron !

c) Ah oui effectivement, je me rends compte que je n'avais pas vraiment réfléchi pour cette question...
f) D'accord, tout simplement

b) D'accord, je vois, je m'y remets

Merci pour ton aide
Je reviens quand ça bloque

Je vois où tu veux en venir pour la b) du deuxième exercice, mais a-t-on le droit d'être aussi "direct' ?
Ne faut-il pas passer par une égalité de Bezout intermédiaire, du style : au + vb² = d, pour ensuite aller chercher celle de la question précédente ?

Ou alors plus simplement, comme d divise a et d divise b², alors d divise toute combinaison linéaire de a et b², et a, u et v étant des entiers relatifs, alors d divise bua + vb² = b ?
C'est mieux du coup oui

Prauron t'es toujours là ? J'ai besoin de toi

Ou alors plus simplement, comme d divise a et d divise b², alors d divise toute combinaison linéaire de a et b², et a, u et v étant des entiers relatifs, alors d divise bua + vb² = b ?

Oui c'est exactement ce que j'ai fait.

Hormis cette question b), je suis confronté à d'autres difficultés :

-... la question c) me pose problème ( ), je ne vois pas trop comment exploiter le fait que a et b² soient premiers entre eux, car en tentant des trucs avec des égalités de Bezout, ça ne me mène pas à grand chose
- ensuite, c'est la question e) de la partie B qui m'embête, je ne vois vraiment pas comment faire, en essayant d'obtenir D² avec une égalité de Bezout, ça me donne un truc vraiment moche, et sinon, je ne vois vraiment pas comment utiliser les parties étrangères (à quoi cela me mène que les parties étrangères soient premières entre elles ?), ni comment utiliser la Partie A, (dans le e., a et b ne sont pas forcément premiers entre eux, mais je pense que le "forcément" me gêne).

Merci

Le 14 février 2016 à 15:48:43 Prauron a écrit :

Ou alors plus simplement, comme d divise a et d divise b², alors d divise toute combinaison linéaire de a et b², et a, u et v étant des entiers relatifs, alors d divise bua + vb² = b ?

Oui c'est exactement ce que j'ai fait.

Ah ok, c'est plus simple ouais

La question b) permet d'affirmer que (a et b premiers entre eux) => (a et b² premiers entre eux).
En remplaçant a par b² et b par a dans cette implication, on obtient (b² et a premiers entre eux) => (b² et a² premiers entre eux). D'où c).

Qu'est-ce que le théorème des parties étrangères ?

Pas besoin de le savoir en fait.

Si D = pgcd(a,b), alors a = Da' et b = Db' avec a' et b' premiers entre eux. Donc (a')² et (b')² sont premiers entre eux d'après la partie A.
pgcd(a²,b²) = pgcd(D²a'²,D²b'²) = D²pgcd(a'²,b'²) = D² = pgcd(a,b)²

Le 14 février 2016 à 16:06:30 Prauron a écrit :

> Si D = pgcd(a,b), alors a = Da' et b = Db' avec a' et b' premiers entre eux.

Voila, tu viens d'énoncer le théorème des parties étrangères

c) Ah ok, pas besoin de calcul, c'est juste un "jeu" sur les implications
e) Ah ouais, joli

Je reprends ça alors.

Je me lancerai plus tard dans la Partie C, donc je reviendrai dans la soirée je pense

Merci beaucoup

Re

Je m'y suis remis et... je bloque à la partie C
En fait, ce sont les questions h) et i) qui me posent problème :
- pour la h), j'avais pensé à un raisonnement par l'absurde, mais en fait ça ne m'avance pas plus que ça, et je vois pas vraiment comment faire autrement pour montrer rigoureusement qu'il n'y a que deux diviseurs possibles
- pour la i), je vois bien qu'il faut que je procède en démontrant les deux sens de l'équivalence, mais, en partant de delta = 5, je n'arrive pas, en jouant avec la définition du PGCD, à obtenir "5 divise ". Par contre l'autre sens c'est bon. En gros j'ai réussi à montrer que 5 divise 2n + 5 et que 5 divise 10 ( ), donc 5 divise delta, et comme delta vaut 1 ou 5, alors delta = 5.

Merci

J'ai besoin de vous les amis

Pour la h tu peux traiter les cas uns par uns.
Ton pgcd divise 10, donc ça peut être 1, 2, 5 ou 10. Il te suffit de montrer que ça ne peut pas être 2 ou 10, et si tu veux, tu peux même donner un exemple où c'est 1 et un exemple où c'est 5.

Pour la i, ton raisonnement est correct. Pour l'autre sens, tu pars de delta = 5 et tu montres que delta divise n, c'est à peu près pareil.

Salut
Donc pour la h), j'ai montré par l'absurde que delta était différent de 2 et 10, à l'aide des congruences, par contre, je ne sais pas si c'est très rigoureux.
En fait, j'ai dit, par exemple; que si delta = 2, alors 2n+5 = 0 [2]. Or, 2n + 5 = 1 [2] donc c'est pas bon. Et idem pour delta = 10. Ce qui me gène cependant, c'est que pour chaque cas, je suis parti de n=0, modulo le delta que l'on souhaite, et le truc, c'est que je ne sais pas si j'ai le droit de dire que n est divisible par le delta que je souhaite, raisonnement par l'absurde ou non (remarque, j'ai l'impression que ça se rejoint avec la question i....)
Ensuite, pour la i), c'est juste qu'en partant de delta = 5, je n'arrive pas à obtenir une combinaison linéaire me permettant d'obtenir uniquement "5 divise n", donc je bloque encore

Besoin de vous les copains