Décomposition
dans Arithmétique
Bonjour,
Soit la congruence initiale $X^m\equiv B^n\pmod{C}$, ou $X$ est inconnu et où $C$ est un nombre composé dont la décomposition en facteurs premiers (distincts) donne : $C=p_1^{k_1}\times p_2^{k_2}\times \cdot\cdot\cdot\times p_z^{k_z}$, pour un certain entier naturel non nul $z$.
Ce qui suit est-il correct ?
Pour résoudre la congruence initiale, c'est-à-dire trouver toutes les valeurs de $X$ rendant vraie cette congruence, donner à $X$ chacune des valeurs entières comprises entre $0$ et $C-1$ équivaut à résoudre simultanément les $z$ congruences suivantes (Edit : "équivaut"="conduit aux mêmes solutions"):
1) $X^m\equiv B^n\pmod{p_1^{k_1}}$
2) $X^m\equiv B^n\pmod{p_2^{k_2}}$
etc.
z) $X^m\equiv B^n\pmod{p_z^{k_z}}$
[de sorte que, si une de ces $z$ congruences au moins n'a pas de solution, alors la congruence initiale n'a pas non plus de solution.]
(Edit : A la suite d'une remarque de Goleon, j'ai mis cette dernière phrase entre crochets pour en minimiser l'importance.)
Merci d'avance,
Sneg.
Soit la congruence initiale $X^m\equiv B^n\pmod{C}$, ou $X$ est inconnu et où $C$ est un nombre composé dont la décomposition en facteurs premiers (distincts) donne : $C=p_1^{k_1}\times p_2^{k_2}\times \cdot\cdot\cdot\times p_z^{k_z}$, pour un certain entier naturel non nul $z$.
Ce qui suit est-il correct ?
Pour résoudre la congruence initiale, c'est-à-dire trouver toutes les valeurs de $X$ rendant vraie cette congruence, donner à $X$ chacune des valeurs entières comprises entre $0$ et $C-1$ équivaut à résoudre simultanément les $z$ congruences suivantes (Edit : "équivaut"="conduit aux mêmes solutions"):
1) $X^m\equiv B^n\pmod{p_1^{k_1}}$
2) $X^m\equiv B^n\pmod{p_2^{k_2}}$
etc.
z) $X^m\equiv B^n\pmod{p_z^{k_z}}$
[de sorte que, si une de ces $z$ congruences au moins n'a pas de solution, alors la congruence initiale n'a pas non plus de solution.]
(Edit : A la suite d'une remarque de Goleon, j'ai mis cette dernière phrase entre crochets pour en minimiser l'importance.)
Merci d'avance,
Sneg.
Réponses
-
Salut Sneg,
Oui, mais mais dis moi, est-ce que tu perds la mémoire ou bien c'est moi ? Car j'ai l'impression que tu as déjà posé la même question :-D -
Bonjour, Goleon,
Si j'ai effectivement perdu la mémoire, je me souviens quand même avoir déjà posé une question similaire dans un autre fil.
Tu avais alors été le seul à me répondre par : " Aucune idée si c'est accepté par des mathématiciens, faut leur demander."
C'est ce que je fais aujourd'hui. -
Salut Sneg
Je ne suis pas mathématicien, mais si tu veux mon point de vu d'honnête citoyen :-D:-D
Comme je t'ai dit ça manque de précision à mon goût, car tu utilises le mot "équivaut" et je ne sais pas comment faire pour répondre à la question suivante.
Résoudre : $$
X^2 = 3^2 \pmod{7 \times 5 \times 3}.
$$ Les solutions $\pmod{7}$, $\pmod{5}$ et $\pmod{3}$ sont évidentes (je sais faire) donc si ça équivaut vraiment, je dois bien avoir un moyen pour calculer toutes les solutions $\pmod{7 \times 5 \times 3}$, tu ne trouves pas ?
Voilà tout !
Note : après si ton but c'est de montrer que la congruence de base n'a pas de solution, alors je trouve ça très lourd ce que tu dis, puisque si la congruence initiale a une solution $A^n = B^m \pmod{C}$ alors $C$ divise $A^n-B^m$ et comme $p_i^{k_i}$ divise $C$ et bien $p_i^{k_i}$ divise $A^n-B^m$ et donc $A^n=B^m \pmod{p_i^{k_i}}$ et donc c'est ok, sans dire que ça équivaut ! -
Pardon, Goleon, j’ai un contretemps. Je reviendrai dès que possible.
-
Goleon,
Voici comment je résous ton problème :
$X^2\equiv 9\equiv 0 \pmod{3}$ possède une solution : $X\equiv 0$.
$X^2\equiv 9\equiv 4 \pmod{5}$ possède deux solutions : $X\equiv 2$ et $X\equiv 3$.
$X^2\equiv 9\equiv 2 \pmod{7}$ possède deux solutions : $X\equiv 3$ et $X\equiv 4$.
Le tableau des solutions est donc le suivant :
$$
\begin{array}{|c|c|c|c|c|}
\hline
& \pmod{3} & \pmod{5} & \pmod{7} & \Rightarrow \pmod{105} & \\
\hline
X\equiv & 0 & 2 & 3 & 87 & \\
\hline
X\equiv & 0 & 2 & 4 & 102 & \\
\hline
X\equiv & 0 & 3 & 3 & 3 & \\
\hline
X\equiv & 0 & 3 & 4 & 18 & \\
\hline
\end{array}$$
Donc, quatre solutions : $3$, $18$, $87$ et $102$.
Ce sont les mêmes solutions que celles que l'on trouverait en donnant à $X$ la valeur de chacun des entiers appartenant à l'intervalle $[0, 104]$. C'est pourquoi je parle de méthodes "équivalentes" ("qui conduisent aux mêmes solutions").
La méthode générale, proposée dans le message initial, semble reposer sur le théorème des restes chinois. Mais j'aimerais avoir l'avis des mathématiciens sur sa validité.
Encore merci. -
Salut Sneg,
Est-ce que tu peux expliquer comment as-tu construit ton tableau ? Juste le $87$ par exemple.
Oui il y a des histoires de théorème chinois dans le premier message, mais pour être plus clair lorsque tu dis : "de sorte que, si une de ces
z congruences au moins n'a pas de solution, alors la congruence initiale n'a pas non plus de solution." Si c'est uniquement cette conclusion qui t'intéresse, alors tu n'as pas besoin du théorème que tu cites. -
Bonsoir, Goleon,
Dans chaque ligne horizontale du tableau, on range une solution modulo 3, une solution modulo 5 et une solution modulo 7. Il faut évidemment, d'une part, s'arranger pour avoir à chaque ligne un trio différent de ceux que l'on trouve dans les autres lignes et, d'autre part, bien répertorier tous les trios différents possibles.
Ensuite, pour ce qui est de la ligne horizontale terminée par $87$ par exemple, il s'agit de trouver le nombre entier appartenant à l'intervalle $[0,104]$ et simultanément congru à 0 modulo 3, à 2 modulo 5 et à 3 modulo 7. C'est 87.
Maintenant, pour ce qui est de la lourdeur de ma méthode pour déterminer si une congruence a des solutions ou pas, je ne suis pas du même avis que toi. Comparons nos méthodes à partir d'un cas qui m'est évidemment favorable :-) :
La congruence $X^6\equiv 5\pmod{30021}$ possède-t-elle des solutions (à résoudre sans recourir à la programmation informatique) ?
La méthode du message initial donne :
Le nombre $30021$ se décompose en facteurs premiers comme ceci : $30021=3\times10007$
Il se fait que $X^6\equiv5\equiv 2\pmod{3}$ n'a pas de solution, cela se vérifie facilement.
Par conséquent, rien qu'en calculant cela, on sait que la congruence $X^6\equiv 5\pmod{30021}$ n'a pas non plus de solution...pour autant que ma méthode soit valide.
En fait, je ne sais pas trop quelle méthode tu utiliserais. -
Salut Sneg,
1. On ne s'est pas compris. Je refais !
Disons que tu veux expliquer a quelqu'un (ici c'est moi le quelqu'un) que la congruence $X^6 = 5 \pmod{3 \times 10007}$ n'a pas de solution. Toi tu utilises ce que tu as écrit dans ton premier message (théorème chinois) et ensuite tu fais les choses avec $\pmod{3}$. Ok, mais comme je suis ultra-chiant je vais te demander de m'expliquer la démonstration de ton premier message et tout plein de question car je suis chiant :-D
$\bullet$ Ce que je veux te dire c'est que tu n'as pas besoin de ton premier message pour faire exactement la même chose que ce tu dis, et donc on n'a même pas a demander l'avis d'un mathématicien puisqu'on peut le faire tout seul !
En effet, supposons que $a$ soit une solution de ta congruence, alors $a^6-5$ est divisible par $3 \times 10007$ et en particulier $a^6-5$ est divisible par $3$ et donc $a^6 = 5 \pmod{3}$ et là je fais pareil que toi !
Tu vois, pas de théorème chinois, j'ai juste dis que $3$ divise $3 \times 10007$ et j'ai gardé la simplicité de ta solution, c'est juste ce que je voulais te dire ! Donc même méthode mais présentation différente, c'est tout … Est-ce que l'on s'est compris ?
2. D'accord pour la construction de ton tableau. Est-ce que tu sais que l'on peut trouver le nombre $87$ sans avoir besoin de tester jusqu'à $104$ ? C'est une histoire un peu tordu d'identité de Bezout !
Exemple : Avec deux nombres seulement car c'est plus simple, disons $ 3 \times 7$. Je pose (j'impose sans expliquer) : $\phi(u,v) = 7v -6u$, ici $u \in \{0,1,2\}$ et $v \in \{0,\dots, 7\}$ si tu veux. Et on a la propriété suivante
$$
\phi(u,v) = u \pmod{7} \qquad \text{et} \qquad \phi(u,v) = v \pmod{3}
$$
Donc si tu cherches $x$ tel que $x = 2 \pmod{3}$ et $x = 5 \pmod{7}$ et bien je dis que c'est $$\phi(5,2) = 7 \times 2 -6 \times 5 = 14-30 = -16 = 5 \pmod{21}$$
Si tu ne connais essayes avec d'autres nombres que $2$ et $5$. Perso, même si j'ai déjà fais plusieurs fois je suis toujours fasciné par ce truc :-D
Avec trois nombres comme $3 \times 5 \times 7$ c'est plus complexe de trouver $\phi$ mais on peut le faire grâce à Bézout ! -
Entièrement d'accord, Goleon, et merci pour ta méthode de calcul que je testerai ce week-end.
Maintenant, dis-moi si je ne me trompe, la question du message initial n'a pas encore reçu de réponse. (J'y ai mis entre crochets la dernière phrase pour en minimiser l'importance.) -
@Sneg Peux-tu montrer cette version du théorème des restes chinois :
$C= \prod_{j=1}^J p_j^{k_j}$, soit $l_j = \prod_{i\ne j} p_i^{k_i}$ et $d_j l_j \equiv 1 \bmod p_j^{k_j}$
Ssi $\forall j, x_j^m \equiv B\bmod p_j^{k_j}$ alors
$$ \prod_{j=1}^J ( (x_j-1) d_j l_j + 1)^m \equiv B \bmod C$$
De plus $X \equiv \prod_{j=1}^J ( (X-1) d_j l_j + 1) \bmod C$ implique que tous les solutions sont de cette forme.
L'étape d'après c'est de comprendre la structure de groupe de $\Z/p_j^{k_j}\Z^\times$ pour exprimer toutes les solutions en terme des générateurs des groupes cycliques. -
Merci, Namiswan et reuns.
Non, reuns, je ne le peux pas. On atteint là les limites de mes connaissances et de mes aptitudes. -
En fin de compte, reuns, ta réponse à la question initiale de ce fil est-elle «oui» ?
-
Au risque d'insister lourdement - pardon à l'avance - comment feriez-vous pour résoudre par les mathématiques la congruence suivante :
$x^2\equiv 1\pmod{1797}$
Merci.
(Mes solutions : 1, 598, 1199 et 1796.) -
Factorisation $1797 = 3 \times 599$, résolution de $x^2 \equiv 1$ mod $3$ et $x^2 \equiv 1$ mod $599$, théorème chinois.
-
Grand merci, Poirot.
C’est comme ça aussi que j’ai fait.
Une dernière question, quand le module est un nombre premier $p$, la congruence $x^2\equiv 1 \pmod{p}$ n’a jamais que deux solutions, $1$ et $-1$ ?
Merci. -
Salut Sneg,
Alors faire attention à $p=2$ qui est le nombre premier le plus pourri de l'univers et qui fait que $1=-1$, et donc une seule solution. sinon oui -
Merci aussi, Goleon.
-
Sneg
Tu as utilisé l'informatique pour trouver $1199$ ? -
non. :-)
-
Bonjour
Au cas où, 598 et 1199 sont opposés modulo 1797
de même que 1 et 1796
En fait cet exemple peut se généraliser
Si $p,q$ sont deux nombres premiers distincts,
avec $p$ ne divisant pas $2a$, $q$ ne divisant pas $2a$,
l'équation $x^2\equiv a^2 (pq)$
a exactement, modulo ($pq$), 4 solutions :
$\pm a,\pm a(up-vq)$,
avec $up+vq=1$, relation de Bezout, $p$ et $q$ étant premiers entre eux (le couple $(u,v)$ n'est pas unique)
si $p=3,q=599$, on a $u=200,v=-1$
si $p=5,q=7$, on a $u=3,v=-2$
Je laisse le lecteur préciser les hypothèses pour avoir 1 seule solution, que 2 solutions.n
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 23
+16 Invités