Forum de mathématiques - Bibm@th.net

On part donc d'une configuration [tex]0 < n_1 \leq n_2 \leq n_3[/tex]. Bien sûr, en cas d'égalité de deux des 3 nombres, on vide l'un dans l'autre et l'algorithme s'arrête. Je vais appeler les récipients R1, R2 et R3.
On écrit la division euclidienne de [tex]n_2[/tex] par [tex]n_1[/tex] : [tex]n_2 = q \times n_1 + r,\ 0 \leq r < n_1[/tex] et on va montrer comment vider R2 jusqu’à [tex]r[/tex].
L'observation principale est que, à chaque fois qu'on verse de R2 vers R1, le contenu de R1 progresse selon le schéma [tex]2^n \times n_1[/tex] et le contenu de R2 selon le schéma [tex](q - \sum_0^n 2^i)n_1 + r[/tex]. Bien sûr, on n'arrivera pas à annuler [tex]q[/tex] en règle générale (ça marche uniquement dans les cas où existe un [tex]k[/tex] tel que [tex]q = \sum_0^k 2^i = 2^{k+1}-1[/tex]), et c'est là qu'intervient R3.
Donc, on écrit [tex]q[/tex] en base 2 : [tex]q = \sum_0^k \delta_{2^i}\;\delta_k=1,\, (\delta_i)_{0,k-1}\in \{0,1\}[/tex] ensuite, on regarde chaque [tex]\delta_i[/tex] en partant de [tex]i=0[/tex]. Si [tex]\delta_i=1[/tex], on verse de R2 dans R1, et si [tex]\delta_i=0[/tex], on verse de R3 dans R1 (R3 contient plus de litres que R2, donc, ça sera toujours possible). Ce procédé supprime donc de [tex]q[/tex] toutes les puissances de 2 telles que [tex]\delta_i=1[/tex] et donc annule [tex]q[/tex].
On se retrouve donc comme voulu avec R2 contenant [tex]r[/tex] litres. Soit [tex]r=0[/tex] et l'algorithme s'arrête, soit on recommence le procédé avec R2 devenant R1 et les deux autres triés correctement.

[EDIT] Pour plus de rigueur, je montre ici pourquoi il sera toujours possible d'utiliser R3 quand [tex]\delta_i=0[/tex].
J'écris [tex]n_3 = q_3 \times n_1 + r_3,\ 0 \leq r_3 < n_1[/tex]. Comme [tex]n_3 > n_2[/tex], alors [tex]q_3 \geq q[/tex] et en particulier [tex]q_3 \geq 2^k[/tex] (c'est le [tex]k[/tex] de l'écriture binaire de [tex]q[/tex]). On en déduit donc que [tex]q_3 > 2^k-1=\sum_0^{k-1}2^i[/tex]. Donc, à l'exception de l'indice [tex]k[/tex], on pourra toujours recourir à R3. Pour l'indice k, on n'a pas à recourir à R3 car [tex]\delta_k=1[/tex]

J'utilise le symbole de legendre [tex]\binom{a}{p}[/tex] et la propriété [tex]\binom{ab}{p}=\binom{a}{p} \times \binom{b}{p}[/tex] qui donne pour les puissance [tex]\binom{a^n}{p}=\binom{a}{p}^n[/tex]
Le critère d'Euler dit que [tex]a^{\frac{p-1}{2}} \equiv \binom{a}{p} \ [p][/tex] pour [tex]p[/tex] premier.

Cas 1:
D'abords, on constate que le nombre en question est pair, on a donc un premier diviseur : 2.
Ensuite, on décompose 2013 en facteurs premier : 2013 = 3 * 11 * 61 et on ecrit [tex]3=\frac{7-1}{2}[/tex].
Le critère d'Euler donne [tex](3^{11 \times 61})^{\frac{7-1}{2}} \equiv \binom{3^{11 \times 61}}{7} \ [7][/tex]
On a par ailleurs [tex]\binom{3^{11 \times 61}}{7}=\binom{3}{7}^{11 \times 61}=(-1)^{11 \times 61}=-1[/tex]
Donc [tex]3^{2013} \equiv -1 \ [7] \Longleftrightarrow 3^{2013} + 1 \equiv 0 \ [7][/tex].
Il s'ensuit donc que [tex]3^{2013} + 1 = 2 \times 7 \times k, k > 1[/tex]

Cas 3:
5 impair, donc [tex]5^{2015}[/tex] est impair, donc [tex]5^{2015}-1[/tex] est divisible par 2
D'autre par 2015=5*13*31 et 5 = (11-1)/2. Donc avec le critère d'Euler, ça donne :
[tex](5^{13*31})^{\frac{11-1}{2}} \equiv \binom{5^{31*13}}{11} \ [11] = \binom{5}{11}^{31*13}=1[/tex]
donc [tex]5^{2015}-1 \equiv 0 \ [11] [/tex]
et finalement [tex]5^{2015}-1 =2 \times 11 \times k, k > 1[/tex]

Cas 2, incomplet:

On constate que [tex]4^{2k+1} \equiv 4 \ [5][/tex], comme par ailleurs 2014=2*19*53, il vient que [tex](2^2)^{19*53} \equiv 4 \ [5][/tex], et donc [tex]2^{2014} +1 \equiv 0 \ [5].[/tex]