Congruences (arithmétique)

Aide à la résolution d'exercices de mathématiques de tout niveau scolaire.
[participation réservée aux utilisateurs inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
kadtex
Utilisateur confirmé
Utilisateur confirmé
Messages : 44
Inscription : dimanche 25 novembre 2012, 18:43

Congruences (arithmétique)

Message non lu par kadtex »

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
kojak
Modérateur général
Modérateur général
Messages : 10450
Inscription : samedi 18 novembre 2006, 19:50

Re: Congruences (arithmétique)

Message non lu par kojak »

Bonjour,

tu peux préciser la référence exacte de ce sujet s'il te plaît ?
Pas d'aide par MP.
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4065
Inscription : mercredi 02 janvier 2008, 23:18

Re: Congruences (arithmétique)

Message non lu par balf »

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.
kadtex
Utilisateur confirmé
Utilisateur confirmé
Messages : 44
Inscription : dimanche 25 novembre 2012, 18:43

Re: Congruences (arithmétique)

Message non lu par kadtex »

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 ?
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4065
Inscription : mercredi 02 janvier 2008, 23:18

Re: Congruences (arithmétique)

Message non lu par balf »

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.
kadtex
Utilisateur confirmé
Utilisateur confirmé
Messages : 44
Inscription : dimanche 25 novembre 2012, 18:43

Re: Congruences (arithmétique)

Message non lu par kadtex »

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!
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4065
Inscription : mercredi 02 janvier 2008, 23:18

Re: Congruences (arithmétique)

Message non lu par balf »

À 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.
kadtex
Utilisateur confirmé
Utilisateur confirmé
Messages : 44
Inscription : dimanche 25 novembre 2012, 18:43

Re: Congruences (arithmétique)

Message non lu par kadtex »

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
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4065
Inscription : mercredi 02 janvier 2008, 23:18

Re: Congruences (arithmétique)

Message non lu par balf »

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.
kadtex
Utilisateur confirmé
Utilisateur confirmé
Messages : 44
Inscription : dimanche 25 novembre 2012, 18:43

Re: Congruences (arithmétique)

Message non lu par kadtex »

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.
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4065
Inscription : mercredi 02 janvier 2008, 23:18

Re: Congruences (arithmétique)

Message non lu par balf »

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.
Répondre