Exo congruences

[seyrinian]

Bonsoir, j'ai un soucis ça va faire plusieurs jours que je penche sur deux exos de congruences et je n'arrive pas du tout à trouver la solution. Je ne saisis même pas la méthode à employer.

Premier exo: Trouver l'ensemble des carrés dans Z/19Z. (Un carré dans Z/19Z est un élément qui est le carré d'un autre.)
Ecrire chaque élément par un nombre compris entre 0 et 18, et séparer les éléments par des virgules.

La réponse est {0,1,4,5,6,7,9,11,16,17} mais je ne vois pas comment en arriver là.

Deuxième exo: Calculer 13/10 dans Z/17Z. Le résultat doit être représenté par un nombre compris entre 0 et 16.

Je n'ai même pas la réponse pour celui là.

Voilà en espérant que vous puissiez m'éclairer merci d'avance.

[zygomatique]

salut

x | 0 |1 | 2 | .... | 18
x² | 0 | 1 | 4 | ....| 1



2e exo :: cherche u et v tels que 10u + 17v = 1 ....

[Ben314]

\begin{tabular}...\end{tabular} =>

2e exo :: cherche u et v tels que 10u + 17v = 1 ....

Voire même 10u + 17v = 13 dont tu peut trouver une solution particulière en moins de 7 secondes 47 centièmes grâce à la méthode ArchiHyperSynthétique de...

[seyrinian]

Malheureusement pour le second exo ce n'est pas la bonne solution le logiciel ne l'accepte pas pourtant j'ai bien appliqué la formule. Et après tout pourquoi me dis tu de prendre le 10 et pas le 13?

Pour le premier exo je ne comprends rien à ce que tu veux dire, je sais bien que 2²=4 mais ça me mène nulle part :)

Il faut surement utiliser des formules de congruences mais j'ignore lesquelles

[Ben314]

Pour le premier exo je ne comprends rien à ce que tu veux dire, je sais bien que 2²=4 mais ça me mène nulle part
Malheureusement pour le second exo ce n'est pas la bonne solution le logiciel ne l'accepte pas pourtant j'ai bien appliqué la formule. Et après tout pourquoi me dis tu de prendre le 10 et pas le 13 ?

Pour l'exo 1) il n'y a aucune "formules" de congruence à connaitre, juste... savoir ce qu'est une congruence.

Par exemple, pour t'aider, zygomatique t'a donné la dernière valeur : 18²=324 et, si on pose la division de 324 par 19, ça donne 324=17x19+1 donc 324 est congru à 1 modulo 19 : on met 1 en dessous de 18 (en fait il y a une astuce, mais... on verra plus tard...)
C'est au dessus de tes moyen de remplir le tableau ?

Pour l'exo 2), tu parle de quel logiciel ?

Rappel (pour l'exo 2) : En général, le nombre qu'on note , c'est celui (s'il existe et est unique...) qui, quand on le multiplie par donne donc ce qu'on te demande de faire, c'est de trouver quel(s) éventuel(s) donnent .
Et vu le niveau impressssssionant que tu as en congruence, je me demande si ça serait pas plus instructif que tu cherche le en tâtonnant : est ce que ça marche avec 0 ? avec 1 ? avec 2 ? . . .

[zygomatique]

ben bien sur tu calcules les carrés des entiers inférieurs à 18 .... puis leur congruence modulo 19 !!!

deuxième exo : que veut dire dans ton énoncé 13/10 ?

[seyrinian]

Bah à la base c'est un tp donc les exemples dans les exos changent à chaque fois, et là en l'occurence le logiciel m'a mis faux en appliquant la méthode de l'exo 2.
Pour l'exo 1 j'avais pas comrpis de cette manière mais avec ton explication en effet c'est simple.
Mais j'avais fait une tite erreur aussi sur l'exo 2 j'ai compris aussi maintenant que tu as bien détaillé.
Merci bien

[seyrinian]

Le 13 sur 10 est un quotient dans l'ennoncé et il faut résoudre la solution dans 17z

[seyrinian]

Je vous remercie je viens de comprendre et de trouver les bons résultats :)
Néanmoins il me reste un dernier exo sur les pgcd cette fois-ci et bien que je sais qu'il faille utiliser l'identité de bezout je ne sais pas comment arriver au résultat correct. Je crois qu'il y a un truc à faire en plus. Voici l'exo:
Au restaurant, n personnes ont pris le menu A qui coûte 18 euros, m personnes ont pris le menu B qui coûte 15 euros. Au total la somme de 921 euros a été encaissée. Combien de personnes ont pris le menu A ? le menu B ? Donner une solution pour ce problème.
Quel est le nombre de solutions possibles ?

[Ben314]

C'est effectivement du "Bézout+" :
L'énoncé te demande de résoudre 18A+15B=921 où A et B sont des entiers naturels (un "nombre de personnes" ne peut pas être égal à 3.27 ni à -5 !!!)
Normalement, si tu as vu Bézout, tu doit savoir comment trouver les solutions dans Z.
Il te suffit... de le faire puis une fois les solutions dans Z trouvées, de regarder lesquelles sont positives.

[seyrinian]

Le soucis est que l'applicaiton de bezout que l'on vu en cours fonctionne lorsque le pgcd=1 ce qui n'est pas le cas ici il est de 921...

[Ben314]

Quand tu as à résoudre 18A+15B=921, avant même de regarder ce que tu as à droite du =, tu commence par regarder le pgcd des coeff, donc ici de 18 et de 15.
M..., ils ne sont pas premier entre eux, leur pgcd c'est 3 ce qui signifie que tout nombre de la forme 18A+15B va évidement être multiple de 3.
Si le nombre à droite du égal n'est pas lui même multiple de 3, c'est foutu, il n'y a pas de solutions.
Ah oui, mais là, 921 est multiple de 3 (étonnant non :ptdr:). Bon, alors on fait quoi ?
Ben vu qu'en fait tout est multiple de 3 on... divise tout par 3 (malin comme méthode non :karate:)
Ca donne donc 6A+5B=307 et, de façon surprenante :zen:, maintenant pgcd(6,5)=1.
Donc Bézout te chuchote à l'oreille qu'on peut trouver u et v tels que 6u+5v=1 <= Que peut-on prendre pour u et v ?
(heureusement qu'il est là Bézout, sinon on s'en serait pas douté :dingue2:)
Oui, sauf que c'est pas 1 qu'on voulait, mais 307.
Comment pourrait on bien faire pour passer de 1 à 307 :look_up: ?

[seyrinian]

Bon j'ai retesté mais pas moyen, les exemples changent à chaque essai cette fois si le pgcd donne directement 1. Mais dans tous les cas je ne comprends pas une fois que l'on a trouvé x et y pour ax+by=1 et qu'il faut passer au nombre recherché. Il ne suffit pas bêtement de multiplier je suppose. D'autant qu'un de mes nombres est négatif je ne vois pas comment me débrouiller. Désolé :(

[zygomatique]

comme ben314 te l'a expliqué on a transformé 3.6a + 3.5b = 3.x en 6a + 5b = x

il semble naturel qu'une fois avoir trouvé u et v tels que 6u + 5v = 1 alors 6(307u) + 5(307v) = 307

....

[seyrinian]

Pour ça je suis tout à fait d'accord le problème est que je me retrouve toujours avec une solution positive et une négative. Et comme on est pas dans les congruences je vois mal comment la transformer (je suis ptet aveugle ^^)
Et pour la question sur les solutions bah cette technique d'euclide ne va révéler qu'un couple de solution non? Or l'exercice m'a dit qu'il y en avait plusieurs

[zygomatique]

18a + 15b = 921 <=> 6a + 5b = 307

or 6*1 + 5(-1) = 1

donc 6 * 307 + 5(-307) = 307

6*307 + 5(-307) = 307
6a + 5b = 307

par soustraction

6(a - 307) + 5(b + 307) = 0 <=> 6(307 - a) = 5(b + 307)

donc 307 - a est multiple de 5 <=> a = 307 - 5k
et b + 307 est multiple de 6 <=> b = -307 + 6k

on vérifie bien que 6(307 - 5k) + 5(-307 + 6k) = 307

or 307 - 5k >0 <=> ...
et -307 + 6k > 0 <=> ...

donc k peut prendre les valeurs ....

...