Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. TerminaleForum de terminale ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau terminale
Partager :

comment utiliser les congruences

Posté par
marc2016 08-01-16 à 06:06

Bonjour,svp j ai un question exactement la question 3 que je n arrive pas trouver une solution
est il possible de me proposer une méthode a suivre pour pouvoir la résoudre
comment utiliser les congruences pour résoudre ce type de question  
j ai essayé de résoudre les deux premières questions

exercice :


On considère dans ZxZ , l'équation ( E ) : 7x + 5y = 3276.
1) a)vérifier que(308,224) est solution de l équation(E)
b) Résoudre l équation (E)
  2) soit (x,y) une solution de (E)
   a)Décomposer en facteurs premiers l entier 3276
  b) donner le nombre de diviseurs positifs de 3276
   c)En déduire les valeurs possibles de PGCD(x,y)

3) en utilisant les congruences
   a) Déterminer les couples (x,y) solutions de l équation (E) tels que PGCD(x,y)=2
    b) Déterminer les couples (x,y) solutions de l équation (E) tels que PGCD(x,y)=3
    c)Déterminer les couples (x,y) solutions de l équation (E)
tels que PGCD(x,y)=7
   d) Déterminer les couples (x,y) solutions de l équation (E)
tels que PGCD(x,y)=13
  e) Déterminer les couples (x,y) solutions de l équation (E)
tels que PGCD(x,y)=36


Correction
1) a)  7.308  +  5.224 = 3276 signifie ( 308 , 224 ) est une solution de ( E ) .
b) 7x + 5y = 6 =  7.3 08 +  5224 signifie 7. ( x - 308 ) = 5 ( 224 - y )
7 divise 5 ( 224 - y ) et 7 et 5 sont premiers entre eux donc
D après le théorème de gauss on  7 divise (224- y ) d'où 224- y = 7k  avec k de  Z .
On a 7. ( x - 3 08) = 5.7.k  signifie  x = 5.k + 308  donc  x=5k+308 , y=-7k+224 ) ; k   de Z
Réciproque : pour tout k  Z , 2( 5k+308) + 5(-7k+224) = 3276 donc
( 5k+308 , -7k+224 ) ; k  Z sont les solutions de ( E ) .
2) soit ( x , y ) une solution de ( E ) .
a)3276=2^2 .3^2.13.7
b) le nombre des diviseurs positifs de 3276 est égale à (2+1).(2+1)(1+1).(1+1)=3.3.2.2=36
3276 possède 36 diviseurs
c)On pose d =pgcd( x , y ); d divise x et d divise y alors d divise 7x+5y
Donc d divise 3276
d'où d  appartient a l ensemble suivant {1 , 2 , 3 , 4,6, 7, 9,12,13 , 14,18 ,21,26,28,36, 39,42,52,6378,84,91,117,126,156182,234,252,364,468,546,819,1638,3276} .
3) a)? b)?c)?d)?

si possible de m expliquer comment utiliser les congruences pour répondre a cette question .

merci pour votre aide

Posté par
Taigare : comment utiliser les congruences 08-01-16 à 14:56

Bonsoir,
je pense que cela pourrais t'aider

https://www.ilemaths.net/sujet-pgcd-congruence-et-equation-641640.html

Posté par
marc2016re : comment utiliser les congruences 08-01-16 à 15:37

bonjour ,Taiga
merci pour le lien mais je n est rien compris
je cherche une méthode pour repondre à la question et si possible une réponse

Posté par
lakere : comment utiliser les congruences 08-01-16 à 18:08

Bonjour,

3)a) Pour que PGCD(5k+308;-7k+224)=2, il faut que:

  A) 2 divise 5k+308 et -7k+224 donc que k\equiv 0\;\;[2]

autrement dit que k soit pair.

   On pose k=2p

   PGCD(10p+308;-14p+224)=2PGCD(5p+154;-7p+112)=2  

  PGCD(5p+154;-7p+112)=1

B) 4 ne divise pas 5k+308 et -7k+224

  donc que 2 ne divise pas 5p+154 et -7p+112

  Une disjonction des cas modulo 2 donne p\equiv 1\;\;[2], autrement dit p impair.

C) 3 ne divise pas  5k+308 et -7k+224

   ou encore 3 ne divise pas  5p+154 et -7p+112

Une disjonction des cas modulo 3 donne p\not\equiv 1 \;\;[3]

D) 7 ne divise pas  5k+308 et -7k+224

   ou encore 7 ne divise pas  5p+154 et -7p+112

Une disjonction des cas modulo 7 donne p\not\equiv 0 \;\;[7]

E) 13 ne divise pas  5k+308 et -7k+224

   ou encore 13 ne divise pas  5p+154 et -7p+112

Une disjonction des cas modulo 13 donne p\not\equiv 3 \;\;[13]

En résumé, les couples solutions de (E) dont le PGCD est 2, sont les couples de la forme:

   (10p+308;-14p+224) où p est impair, p\not=3k+1, p\not=7k et p\not=13k+3

C' est assez pénible à faire ...

Posté par
marc2016re : comment utiliser les congruences 08-01-16 à 20:57

Bonjour,lake
merci pour votre correction qui est très claire et bien expliquer
j aime vous proposer comment j ai compris votre démarche
pour le cas PGCD(x,y)=2  il faut que 2 divise x et y à la fois et il faut ajouter la condition suivante 3,4, 7 et 13 ne divise pas x et y autrement les multiples de 2 qui forme la décomposition en facteur premier de 3276=2^2.3^2.7.13
j aime bien écrire les conditions a réaliser pour chaque cas ( c est ici mon blocage c est au niveau des conditions
pour le cas PGCD(x,y)=d   ou d est un élément des diviseurs de 3276
li faut écrire d divise x et y  et il faut ajouter une deuxième condition ( c est ici mon blocage chaque fois) que les multiples de d qui se trouve dans l ensemble des diviseurs de d ne divisent pas x et y

prenons l exemple pgcd(x,y)=3^2.7.13=819  donc 819 divise x et y  et 2em condition il faut ajout quelles éléments qui ne divise pas x et y  
c est ici mon problème

svp donner plus d explication car je n est pas compris pour quoi tu as ajouté
la deuxième condition (3,4, 7 et 13 ne divise pas x et y)

merci pour votre coopération avec moi

Posté par
lakere : comment utiliser les congruences 08-01-16 à 21:25

On cherche donc un couple (x;y) solution de (E) tel que d=2

Donc x et y sont pairs.

Si 4 divise x et y, alors 4 divise leur PGCD d et d est un multiple de 4 ce qu' on ne veut pas puisque d=2

Donc 4 n' est pas un diviseur commun à x et y

Si 3 divise x et y, alors 3 divise leur PGCD d et d est un multiple de 3 ce qu' on ne veut pas puisque d=2

Donc 3 n' est pas un diviseur commun à x et y

Si 7 divise x et y, alors 7 divise leur PGCD d et d est un multiple de 7 ce qu' on ne veut pas puisque d=2

Donc 7 n' est pas un diviseur commun à x et y

Si 13\cdots

Mieux comme ça?

Posté par
marc2016re : comment utiliser les congruences 08-01-16 à 21:40

Bonjour ,lake
svp  j ai oublié une question
pourquoi tu n as pas jouté la condition 9 ne divise pas  x et y    

3276=2^2.3^2.7.13=4.9.7.13

merci

Posté par
lakere : comment utiliser les congruences 08-01-16 à 21:44

Mais si 3 ne divise pas x et y, ses multiples, en particulier 9 ne le diviseront pas non plus!

Posté par
marc2016re : comment utiliser les congruences 08-01-16 à 21:45

Salut , lake
oui c est mieux comme ça et plus claire mais je n arrive pas a  comprendre comment tu fait à chaque valeur du PGCD
si possible de prendre un autre cas par exemple d=36
et de me généraliser la méthode a suivre car je  n est pas peu l appliquer
merci

Posté par
lakere : comment utiliser les congruences 08-01-16 à 21:52

Pour d=36=2^2\times  3^2:

Il faut que:

4 et 9 divisent les deux nombres.

7 et 13 ne divisent pas les deux nombres.

Posté par
marc2016re : comment utiliser les congruences 08-01-16 à 21:52

Salut, lake
comment exploiter l écriture décomposition en facteurs premiers
pour une valeur donnée de PGCD =d qui est un des facteurs premiers  de la décomposition

donner moi une règle a suivre pour ne pas oublier une condition

svp lake si je n est encore compris je peu te poser des questions jusque je comprend cette question  

merci

Posté par
lakere : comment utiliser les congruences 08-01-16 à 21:56

Il n' y a pas de "règles".

Il y a des raisonnements à tenir comme à 21h25.

Posté par
marc2016re : comment utiliser les congruences 08-01-16 à 22:11

Salut lake
j aime que tu me donne une méthode  pas une règle
dans le cas générale
c est a dire chaque fois que je fixe une valeurs du PGCD  =d j écrit d divise x ety  et il faut que ???   ( comment choisir les nombres qui ne divisent pas les deux nombres a partir de la décomposition en facteur premiers  
par exemple A= a^2 .b^3.d^5.c^7

retour a notre exemple

3276=2^2.3^2.7.13=4.9.7.13

pour d=3^2.7    il faut que 7 et 9 divisent les deux nombres et les deux autres facteurs du produit 4 et 13 ne divisent pas

pour d=2^2 .3.7.13  il faut que 4,3,,7,13 divisent les deux nombres et 9 ne divise pas les deux nombres

si possible de me corriger

merci

Posté par
lakere : comment utiliser les congruences 08-01-16 à 22:34

Citation :
3276=2^2.3^2.7.13=4.9.7.13

pour d=3^2.7    il faut que 7 et 9 divisent les deux nombres et les deux autres facteurs du produit 4 et 13 ne divisent pas


Ça ne suffit pas: il faut aussi que 2 ne soit pas diviseur commun aux deux nombres sinon d=2\times 3^2\times 7.

Et remarque que si 2 n' est pas un diviseur commun aux deux nombres, 4  ne le sera pas non plus.

Citation :
pour d=2^2 .3.7.13  il faut que 4,3,,7,13 divisent les deux nombres et 9 ne divise pas les deux nombres


Oui.

Posté par
marc2016re : comment utiliser les congruences 08-01-16 à 22:50

Salut lake
merci pour votre aide
je vais essayé de comprendre ça
si j applique ça sur les derniers exemples pour ce soir  et je n arrive pas a comprendre demain je te demanderais de m expliquer de nouveau la démarche a suivre
3276=2^2.3^2.7.13=4.9.7.13
  d=1          2,3,4,9,7,13 ne divisent pas les deux nombres
1)si d=2^2.7=4.7   donc 4 et 7 divisent les deux nombres et 3,9.13 ne divise pas les deux nombres
2) d=2^2.3^2              donc 4 et 9 divisent  les deux nombres et 7 et 13 ne divisent pas
3)d=2^2   3                              4 et 3   divisent les deux nombres et 3,7,13 ne divise pas        

si possible de me corriger

merci

Posté par
lakere : comment utiliser les congruences 09-01-16 à 14:57

Citation :
d=1          2,3,4,9,7,13 ne divisent pas les deux nombres


Oui, mais il suffit d' écrire que 2,3,7 et 13 ne sont pas des diviseurs communs à x et y

Citation :
1)si d=2^2.7=4.7   donc 4 et 7 divisent les deux nombres et 3,9.13 ne divise pas les deux nombres


Oui, mais il suffit d' écrire que 4 et 7 divisent les deux nombres et 3 et 13 ne sont pas des diviseurs communs à x et y

Citation :
2) d=2^2.3^2              donc 4 et 9 divisent  les deux nombres et 7 et 13 ne divisent pas


Oui.

Citation :
3)d=2^2   3                              4 et 3   divisent les deux nombres et 3,7,13 ne divise pas


Regarde ce que tu as écrit...

Posté par
marc2016re : comment utiliser les congruences 09-01-16 à 21:54

salut lake
merci pour votre soutien
svp est ce que je peu énoncé ça comme méthode

si a=p^n.q^m.r^s......g^h    et PGCD(x,y)=d
donc d divise x et y   et il faut éliminer les produits et leurs multiples qui ne figurent pas dans l écriture du PGCD
est ce que c est juste comme technique a appliquer chaque fois

a=  3276=2^2.3^2.7.13=4.9.7.13

d=2^2.3      2 et 3 divisent les deux nombres et 4 et 9 et 7 et 13 ne divisent pas les deux nombres
corriger moi sv

svp expliquer moi encore sur un autre exemple sur a=2^4.3^4.5^2.7^5.11^6
PGCD(x,y)=2 et PGCD(x,y)=15

merci

Posté par
marc2016re : comment utiliser les congruences 09-01-16 à 23:24

Salut lake
svp
j aime bien que tu me complète cette méthode
--(( pour que pgcd(x,y)=d il faut il suffit que x et y soit divisibles par d  et qu ils ne soient pas tous les deux divisibles par ( quoi ???)

merci


Posté par
marc2016re : comment utiliser les congruences 10-01-16 à 19:44

Bonjour lake
svp donner moi plus d explications pour écrire les conditions chaque fois
si possible de repondre a mes deux derniers messages
merci

Posté par
marc2016re : comment utiliser les congruences 12-01-16 à 18:33


Salut lake
peut tu me donner d une façon  générale
pour que pgcd(x,y)=d il faut il suffit que x et y soit divisibles par d  et qu ils ne soient pas tous les deux divisibles par ( quoi ???)

merci


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 !