Exercices math sup : Arithmétique

• $\left\{\begin{array}{rcl} 3x+y&=&32\\ 3x-y&=&1. \end{array}\right.\quad$ Mais ce système n'a pas de solutions entières...
• $\left\{\begin{array}{rcl} 3x+y&=&16\\ 3x-y&=&2. \end{array}\right.\quad$ Dans ce cas, on trouve $x=3$ et $y=7$.
• $\left\{\begin{array}{rcl} 3x+y&=&8\\ 3x-y&=&4. \end{array}\right.\quad$ Dans ce cas, on trouve $x=2$ et $y=2$.

• soit $n+1<b$. Dans ce cas, on peut écrire $n+1=(n+1)b^0$, et on a le résultat avec $p=0$ et $a_0=n+1$.
• soit $n+1\geq b$. Dans ce cas, on réalise la division euclidienne de $n+1$ par $b$. On écrit donc $$n+1=bq+r,\ 0\leq r\leq b-1.$$ On a alors $q\leq n$ et on peut appliquer l'hypothèse de récurrence à $q$ : $q$ s'écrit $$q=\sum_{k=0}^p a_k b^k,\ 0\leq a_k\leq b-1,\ a_p\geq 1.$$ On obtient alors $$n+1=\sum_{k=0}^p a_k b^{k+1}+r=r+\sum_{k=1}^{p+1} a_{k-1} b^k.$$ On obtient alors bien que $n+1$ s'écrit $$n+1=\sum_{k=0}^{p'} a'_k b^k, 0\leq a'_k\leq b-1,\ a'_{p'}\geq 1$$ en posant $p'=p+1$, $a'_k=a_{k-1}$ pour $k= 1,\dots,p'$ et $a'_0=r$.

1. Il suffit d'écrire que $$n=\sum_{k=0}^p a_k b^k=\sum_{k=0}^p a'_k b^k$$ ce qui s'écrit encore, par définition de $\ell$, $$n=\sum_{k=0}^\ell a_k b^k=\sum_{k=0}^\ell a'_k b^k.$$ Ceci s'écrit à son tour $$a_\ell b^\ell+\sum_{k=0}^{\ell-1} a_k b^k=a'_\ell b^\ell+\sum_{k=0}^{\ell-1} a'_k b^k$$ ce qui donne immédiatement le résultat voulu.
2. On écrit simplement que $$\sum_{k=0}^{\ell-1} c_k b^k\leq (b-1)\sum_{k=0}^{\ell-1}b^k=b^\ell-1<b^\ell$$ où on a reconnu une somme géométrique.
3. Supposons par exemple que $a_\ell>a'_\ell$. On a alors, puisque $|a'_k-a_k|\leq b-1$, $$\left|\sum_{k=0}^{\ell-1} (a'_k-a_k)b^k\right|\leq\sum_{k=0}^{\ell-1} |a'_k-a_k| b^k<b^{\ell}\leq (a_\ell-a'_\ell)b^\ell$$ ce qui contredit l'hypothèse faite. On a donc bien démontré l'unicité de la décomposition en base b.

1. Multiplions la relation $y_0=\frac mn x_0-\frac pq$ par $n$. On obtient $$ny_0-mx_0=\frac{-pn}q.$$ Mais $ny_0-mx_0$ est un entier relatif que nous notons $r$. Donc $q(-r)=pn$, ce qui dit bien que $q$ divise le produit $pn$.
2. Puisque $q$ et $p$ sont premier entre eux, ceci est une conséquence du théorème de Gauss.

1. Puisque $m$ et $n$ sont premiers entre eux, le théorème de Bézout nous dit qu'il existe deux entiers $u$ et $v$ tels que $nu-mv=1$. Remplaçant $n$ par $qr$, on obtient le résultat voulu.
2. Multiplions l'équation précédente par $\frac{-np}{q}=-pr$. On trouve $$\frac{-np}q=-pqr^2 u-(-prmv)=n(-pru)-m(-prv).$$ Posons alors $x_0=-prv$ et $y_0=-pru$. $x_0$ et $y_0$ sont bien deux entiers naturels. De plus, ils satisfont $$\frac{-np}{q}=ny_0-mx_0$$ équation qui est équivalente à $$y_0=\frac mn x_0-\frac pq.$$ Le point de coordonnées $(x_0,y_0)$ est donc bien un élément de $\Delta$.

def divise(p,q):
    if ( (q%p) == 0):
         return True
    else:
        return False

def estpremier(p):
    if (p<2):
        return 0
    for i in range(2,p):
        if divise(i,p):
            return 0
    return 1

def phi(n):
    total=0
    for m in range(2,n+1):
        total+=estpremier(m)
    return total

• Si $n\equiv 0\ [4]$, alors $2^n\equiv 1\ [5]$;
• Si $n\equiv 1\ [4]$, alors $2^n\equiv 2\ [5]$;
• Si $n\equiv 2\ [4]$, alors $2^n\equiv 4\ [5]$;
• Si $n\equiv 3\ [4]$, alors $2^n\equiv 3\ [5]$;

• si $y\equiv 0\ [5]$, alors $2y^2\equiv 0\ [5]$;
• si $y\equiv \pm 1\ [5]$, alors $2y^2\equiv 2\ [5]$;
• si $y\equiv \pm 2\ [5]$, alors $2y^2\equiv 8\ [5]\equiv 3\ [5]$.

• Pour $3$, on va prouver que $r_i$ est toujours égal à $1$. C'est vrai pour $i=0$, et si c'est vrai au rang $i$, alors $$10^{r_i}=10=3\times 3+1,$$ et donc $r_{i+1}=1$. On a donc prouvé qu'un nombre est divisible par $3$ si et seulement si la somme de ses chiffres est divisible par 3.
• Pour $9$, le raisonnement est similaire, et on prouve qu'un nombre est divisible par $9$ si la somme de ses chiffres est divisible par 9.
• Pour $10$, on a $r_0=1$, $r_1=0$ et on prouve par une récurrence immédiate que $r_i=0$ pour $i\geq 1$. Un nombre est donc divisible par $10$ si et seulement si son dernier chiffre est nul (bien sûr, on le savait déjà!).
• Pour $11$, on remarque que $r_0=1$, que $r_1=10$, puisque que $r_2=1$, $r_3=10,\dots$. On prouve donc par récurrence sur $k$ que $r_{2k}=1$ et $r_{2k+1}=10$. C'est vrai pour $k=0$, et si c'est vrai au rang $k$, alors $$10r_{2k+1}=100=9\times 11+1,$$ ce qui prouve que $r_{2k+2}=1$. Il vient ensuite $r_{2k+3}=10$, ce qui prouve l'assertion par récurrence. Pour en déduire un critère de divisibilité commode, on remarque que $10\equiv -1\ [11]$. $a$ est donc divisible par $11$ si et seulement si $\sum_{k=0}^n (-1)^k a_k$ est divisible par 11.