Arithmétique

Exercices corrigés d’arithmétique pour Mpsi Pcsi, et Spé Mp, Pc, Psi, posés aux concours Polytechnique, Ens, Mines, Centrale, Ccp, etc.)

Le théorème chinois

Soit {n_1,n_2,\ldots,n_r} dans {\mathbb{N}^*}, premiers entre eux deux à deux. Soit {N=\displaystyle\prod\limits_{k=1}^{r}n_k}.
Il existe un unique x\in[\![0,N-1]\!] tel que x\equiv n_j\mod n_j pour tout j.
Ce résultat est communément appelé théorème chinois. L’objet de cet article est de programmer le calcul de x en Python (deux méthodes).

Coefficients de Bézout

Soient {m,n} dans {\mathbb{N}^*}, avec {m\wedge n=1}.
Il existe une infinité de {(u,v)\in\mathbb{Z}^2} tel que {um+vn=1}.
Il existe en particulier un couple {(u,v)} unique tel que {\left|u\right|\le n/2} et {\left|v\right|\le m/2}.
L’objet de cet article est de programmer deux méthodes (l’une itérative, l’autre récursive) de calcul des deux entiers u et v.