Trouver une fonction à partir de modulo.

fredrick · June 2019

Bonjour,

Je cherche un moyen de trouver la fonction donnant la suite des nombres en fonction du résultat qu'ils donnent avec le reste de plusieurs modulo.
Je donne un exemple pour être plus clair.

Je voudrais pas exemple trouver la suite des nombres dont le résultat modulo 3=1 et modulo 5=2 et modulo7=1

La suite en question 22, 127, 232, 337...
La formule est 105n-83

Je voudrais savoir comment trouver cette formule ?

Je vous remercie.

kioups · June 2019

Théorème des restes chinois ?

claude quitté · June 2019

Soient $a_1, a_2, a_3$ trois entiers premiers deux à deux. On peut chercher $e_1, e_2, e_3$ vérifiant
$$
e_1 \equiv \cases {1 \bmod a_1\cr 0 \bmod a_2 \cr 0 \bmod a_3 \cr} \qquad
e_2 \equiv \cases {0 \bmod a_1\cr 1 \bmod a_2 \cr 0 \bmod a_3 \cr} \qquad
e_3 \equiv \cases {0 \bmod a_1\cr 0 \bmod a_2 \cr 1 \bmod a_3 \cr}
\qquad\quad
e_1 \equiv \cases {1 \bmod a_1\cr 0 \bmod a_2a_3 \cr} \quad
e_2 \equiv \cases {0 \bmod a_1 a_3\cr 1 \bmod a_2\cr} \quad
e_3 \equiv \cases {0 \bmod a_1 a_2\cr 1 \bmod a_3 \cr}
$$
Ensuite, en présence de restes $r_1, r_2, r_3$ modulo $a_1, a_2, a_3$, la somme $x = r_1 e_1 + r_2e_2 + r_3 e_3 + k a_1a_2a_3$, $k \in \Z$, vérifie $x \equiv r_i \bmod a_i$ et on obtient toutes les solutions lorsque $k$ varie dans $\Z$.
Ainsi dans l'exemple :
$$
e_1 = -35 \equiv \cases {1 \bmod 3\cr 0 \bmod 5 \cr 0 \bmod 7 \cr} \qquad
e_2 = 21 \equiv \cases {0 \bmod 3\cr 1 \bmod 5 \cr 0 \bmod 7 \cr} \qquad
e_3 = 15 \equiv \cases {0 \bmod 3\cr 0 \bmod 5 \cr 1 \bmod 7 \cr}
$$
Et, toujours dans l'exemple, $r_1 = 1$, $r_2 = 2$ et $r_3 = 1$. Ce qui conduit à $r_1e_1 + r_2e_2 + r_3e_3 = 22$, $a_1 a_2a_3 = 105$ et au fait que $x = 22 + 105k$ décrit l'ensemble des solutions lorsque $k$ parcourt $\Z$. Note : $22 - 105 = -83$.

Fin de partie · June 2019

si on a deux entiers $a,b$ tels que:
\begin{align} a\equiv u_1 \mod{3}\\
a\equiv u_2 \mod{5}\\
a\equiv u_3 \mod{7}\\
\end{align} et:
\begin{align} b\equiv u_1 \mod{3}\\
b\equiv u_2 \mod{5}\\
b\equiv u_3 \mod{7}\\
\end{align} On a que:
\begin{align} a-b\equiv 0 \mod{3}\\
a-b\equiv 0\mod{5}\\
a-b\equiv 0 \mod{7}\\
\end{align} Et ça c'est équivalent, sauf erreur, puisque $2,5,7$ sont premiers entre eux deux à deux au fait que $a-b$ est divisible par $3\times5\times 7=105$

Trouver toutes les solutions de l'équation en $b$:
\begin{align} b\equiv u_1 \mod{3}\\
b\equiv u_2 \mod{5}\\
b\equiv u_3 \mod{7}
\end{align} revient à trouver une solution particulière de cette équation.

Si $b_0$ est une telle solution, l'ensemble des solutions est composé des nombres de la forme: $b_0+105n$ avec $n$ un entier quelconque.

On a une formule pour obtenir une solution particulière dans un cadre général:
https://fr.wikipedia.org/wiki/Théorème_des_restes_chinois#Généralisation_à_des_nombres_non_premiers_entre_eux

Je pense que cela donne la même solution dans le cas d'espèce que celle exhibée par Claude.

PS:
Même si on ne comprend pas très bien comment a été trouvée cette solution particulière.
On peut vérifier que c'est une solution particulière.