Congruences (arithmétique)

Aide à la résolution d'exercices ou de problèmes de niveau Lycée.

Modérateur: gdm_aidesco

Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Ne poster qu'un exercice (ou problème) par sujet et indiquer son niveau précis dans le titre du message.

Congruences (arithmétique)

Messagepar kadtex » Vendredi 11 Novembre 2016, 18:49

Bonjour

Voici un exo de bac 2016 étranger
a) prouver que 2*2016^(5n+4)+1437^(10n+4) = 0 mod 11, n entier naturel: aucun problème
b)(équation (E): 7x-3y=8 (x;y) entiers
pgcd(7;3)=1 donc des solutions
S={3k+8;7k+16, k entier}, aucun problème
c)d=pgcd(x;y), donner les valeurs possibles de d
d divise 8 donc d={1;2;4;8}
d)Si d=4 donner les solutions de (E)
7x'-3y'=2
S={3k+2;7k+4, k entier}
e) donner le couple (x;y) solution de (E) et qui vérifient 2016^(7x)+1437^(3y)=0 mod 11

2016 mod 11=3
1437 mod 11=7, après quelques lignes de calcul on obtient:
donc 9^x+2^y=0 mod 11

une solution particulière est (1;1) mais elle n'est pas solution de (E)!

Merci pour vos commentaires
kadtex
Déca-utilisateur
 
Messages: 29
Inscription: Dimanche 25 Novembre 2012, 18:43
Statut actuel: Lycée | Terminale S

Publicité

Re: Congruences (arithmétique)

Messagepar kojak » Samedi 12 Novembre 2016, 18:56

Bonjour,

tu peux préciser la référence exacte de ce sujet s'il te plaît ?
pas d'aide par MP
kojak
Modérateur
 
Messages: 10282
Inscription: Samedi 18 Novembre 2006, 19:50
Statut actuel: Actif et salarié | Enseignant

Re: Congruences (arithmétique)

Messagepar balf » Dimanche 13 Novembre 2016, 12:20

Quelques indications:

$9^x+2^y\equiv 0\mod11$ s'écrit aussi $(-2)^x+2^y\equiv 0$. Si l'on remarque que $2$ est d'ordre $10$ modulo $11$ et que $-1\equiv 2^5\mod 11$, l'équation se récrit finalement

$$2^{6x}+2^y\equiv 0\iff 2^{6x-y}\equiv 2^5\mod 11\iff 6x-y\equiv 5\mod10.$$

Il faut donc trouver le point à coordonnées entières, s'il existe, intersection de cette droite définie par son équation cartésienne, et de la droite des solutions précédentes, définie par sa représentation paramétrique.
B. A.
balf
Zetta-utilisateur
 
Messages: 3514
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Congruences (arithmétique)

Messagepar kadtex » Lundi 14 Novembre 2016, 18:25

Bonjour

tu peux préciser la référence exacte de ce sujet s'il te plaît ?


Bac Algérie 2016 rédigé en arabe!

(E):7x-3y=8 équivaut à :y=7/3*x-8/3
La droite passe par A(2;2) et de vecteur directeur U(1:7/3)

Représentation paramétrique:
x=2+t
y=2+7/3*t, t réel

Ta droite:
6x-y=5 mod 10 équivaut à :y=6x-5+10k, k entier
Ce k me gène, je ne sais pas quoi en fare ?
kadtex
Déca-utilisateur
 
Messages: 29
Inscription: Dimanche 25 Novembre 2012, 18:43
Statut actuel: Lycée | Terminale S

Re: Congruences (arithmétique)

Messagepar balf » Mardi 15 Novembre 2016, 01:29

Comme on traite d'entiers, la bonne représentation paramétrique est plutôt

$$x=3t+2,\enspace y=7t+2\quad (t\in\mathbf Z).$$

Il suffit de reporter ces valeurs de $x$ et $y$ pour obtenir l'équation de congruence en $t$

$$10+11t\equiv 5\mod10\iff t\equiv 5\mod 10.$$



B. A.
balf
Zetta-utilisateur
 
Messages: 3514
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Congruences (arithmétique)

Messagepar kadtex » Mercredi 16 Novembre 2016, 18:42

Bonjour

Je reprends ton résultat et je continue:
10+11t=5 mod 10 équivaut à t=5 mod 10
t=5+10q, qentier

et je reporte t dans la représentation paramétrique de la première droite:
x=17+3q
y=37+70q

puis:7*(17+3q)-3*(37+70q)
je développe et je trouve 8

J'ai l'impression que les deux équations
7x-3y=8 et 2016^(7x)+1437^(3y)=0 mod 11
sont vérifiées par les solutions {17+3q, 37+70q } pour tout q entier

Il se peut que je n'ai pas bien saisi ce qu'il faut démontrer!
kadtex
Déca-utilisateur
 
Messages: 29
Inscription: Dimanche 25 Novembre 2012, 18:43
Statut actuel: Lycée | Terminale S

Re: Congruences (arithmétique)

Messagepar balf » Jeudi 17 Novembre 2016, 11:28

À moins que je n'aie pas bien compris ce que représente l'équation E (il y a une certaine ambiguïté à ce sujet, je pense qu'il s'agit de celle désignée dans la question b), on obtient bien une identité: les deux équations ont les mêmes solutions.

Géométriquement cela signifie la chose suivante: puisque l'équation « exponentielle » se traduit finalement par une congruence $6x-y\equiv 5\mod 10$, qui est en quelque sorte l'équation d'une famille de droites parallèles, d'équations $6x-y=5+10k,\enspace k\in\mathbf Z$. Chacune de ces droites, individuellement, coupe la droite $7x-3y=8$ en un point unique. Mais l'ensemble de ces points d'intersections constitue exactement l'ensemble des points à coordonnées entières de la droite $7x-3y=8$.

B. A.
balf
Zetta-utilisateur
 
Messages: 3514
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Congruences (arithmétique)

Messagepar kadtex » Jeudi 17 Novembre 2016, 15:34

Bonjour

À moins que je n'aie pas bien compris ce que représente l'équation E (il y a une certaine ambiguïté à ce sujet, je pense qu'il s'agit de celle désignée dans la question b)

Tout à fait!

Ton explication géométrique est très intéressante, on comprends mieux!

1)Je ne sais pas ce que c'est:
Si l'on remarque que 2 est d'ordre 10 modulo 11

2) comment tu justifies: 2^(6x)+2^y = 0 mod 11 équivaut à 2^(6x-y)...
A moins que ce n'est pas du niveau terminale en france
kadtex
Déca-utilisateur
 
Messages: 29
Inscription: Dimanche 25 Novembre 2012, 18:43
Statut actuel: Lycée | Terminale S

Re: Congruences (arithmétique)

Messagepar balf » Jeudi 17 Novembre 2016, 16:49

1) C'est du vocabulaire de théorie des groupes (plus au programme des lycées depuis belle lurette). Ça veut dire que la première puissance de 2 à être congrue à 1 modulo 11 est $2^{10}$. On vérifie facilement que $2^5\equiv -1\mod 11$, et petit Fermat (combiné au théorème de Lagrange, mais ce n'est plus au programme — on peut en démontrer néanmoins des cas particuliers dans le cadre de l'arithmétique) dit que l'ordre est un diviseur de 10 puisque 11 est premier.

2) C'est que ça peut se récrire $2^{6x}\equiv -2^y$. Comme $-1\equiv 2^5$ (voir ci-dessus), cela donne

$$2^{6x}\equiv2^{y+5}\mod 11\iff 2^{6x-y}\equiv 2^5\mod 11\iff 6x-y\equiv5\mod 10$$

puisque 2 est d'ordre 10.
Est-ce plus clair ?

B. A.
balf
Zetta-utilisateur
 
Messages: 3514
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Congruences (arithmétique)

Messagepar kadtex » Vendredi 18 Novembre 2016, 11:22

Bonjour

Bon, c'est une technique que je ne possède pas!

2^(6x)=2^(5+y) mod 11
2^(6x)=2^5*2^y) mod 11

il se peut que je vais écrire une bêtise

2^(6x)*2^(-y)=2^5 mod 11

2^(6x-y)=2^5 mod 11
ça ressemble à une division or une division est interdite dans les congruences.
kadtex
Déca-utilisateur
 
Messages: 29
Inscription: Dimanche 25 Novembre 2012, 18:43
Statut actuel: Lycée | Terminale S

Re: Congruences (arithmétique)

Messagepar balf » Vendredi 18 Novembre 2016, 23:23

On ne peut pas faire de division en général. Mais on peut faire des divisions modulo $n$ par tous les nombres qui sont inversibles modulo $n$ puisque ça revient à multiplier par l'inverse.

Or précisément, ici, le module est un nombre premier. Donc tout ce qui n'est pas nul modulo ce nombre premier est inversible.
(En termes qui ne sont plus au programme, malheureusement, les entiers modulo $p$, $p$ premier, sont munis d'une structure de corps, et pas simplement d'anneau commutatif).

B. A.
balf
Zetta-utilisateur
 
Messages: 3514
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence


Retourner vers Exercices et problèmes : Lycée

 


  • Articles en relation
    Réponses
    Vus
    Dernier message
  • Congruences
    par perdue15 » Mardi 31 Octobre 2006, 14:44
    2 Réponses
    465 Vus
    Dernier message par perdue15 Voir le dernier message
    Mardi 31 Octobre 2006, 16:07
  • Congruences 2
    par perdue15 » Mardi 31 Octobre 2006, 16:13
    10 Réponses
    509 Vus
    Dernier message par perdue15 Voir le dernier message
    Mardi 31 Octobre 2006, 19:26
  • [TS] Congruences
    par chris107 » Samedi 27 Octobre 2007, 16:19
    19 Réponses
    221 Vus
    Dernier message par chris107 Voir le dernier message
    Samedi 27 Octobre 2007, 19:38
  • [TS] Congruences
    par guiguidu93 » Samedi 18 Octobre 2008, 13:52
    9 Réponses
    969 Vus
    Dernier message par balf Voir le dernier message
    Samedi 18 Octobre 2008, 23:34
  • Congruences
    par 123 » Lundi 20 Octobre 2008, 22:45
    6 Réponses
    602 Vus
    Dernier message par balf Voir le dernier message
    Mardi 21 Octobre 2008, 20:18

Qui est en ligne

Utilisateurs parcourant ce forum: Bing [Bot], MSNbot Media et 4 invités