Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
275 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Trouver une fonction à partir de modulo.

Envoyé par fredrick 
Trouver une fonction à partir de modulo.
il y a six mois
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.
Re: Trouver une fonction à partir de modulo.
il y a six mois
Théorème des restes chinois ?
Re: Trouver une fonction à partir de modulo.
il y a six mois
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$.
Re: Trouver une fonction à partir de modulo.
il y a six mois
avatar
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:
[fr.wikipedia.org]

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.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)



Edité 3 fois. La dernière correction date de il y a six mois et a été effectuée par AD.
Re: Trouver une fonction à partir de modulo.
il y a six mois
Merci pour vos réponses, effectivement c'est bien le problème des restes chinois.
Merci beaucoup pour vos réponses.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 138 309, Messages: 1 342 577, Utilisateurs: 24 794.
Notre dernier utilisateur inscrit hadjer_jlb.


Ce forum
Discussions: 5 132, Messages: 62 220.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page