Page 1 sur 1

Congruences (arithmétique)

MessagePosté: Vendredi 11 Novembre 2016, 18:49
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

Re: Congruences (arithmétique)

MessagePosté: Samedi 12 Novembre 2016, 18:56
par kojak
Bonjour,

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

Re: Congruences (arithmétique)

MessagePosté: Dimanche 13 Novembre 2016, 12:20
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.

Re: Congruences (arithmétique)

MessagePosté: Lundi 14 Novembre 2016, 18:25
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 ?

Re: Congruences (arithmétique)

MessagePosté: Mardi 15 Novembre 2016, 01:29
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.

Re: Congruences (arithmétique)

MessagePosté: Mercredi 16 Novembre 2016, 18:42
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!

Re: Congruences (arithmétique)

MessagePosté: Jeudi 17 Novembre 2016, 11:28
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.

Re: Congruences (arithmétique)

MessagePosté: Jeudi 17 Novembre 2016, 15:34
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

Re: Congruences (arithmétique)

MessagePosté: Jeudi 17 Novembre 2016, 16:49
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.

Re: Congruences (arithmétique)

MessagePosté: Vendredi 18 Novembre 2016, 11:22
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.

Re: Congruences (arithmétique)

MessagePosté: Vendredi 18 Novembre 2016, 23:23
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.