chaîne arithmétique

Merci, Alain, pour la correction (je suis certain que c'est toi, non ?) !
Borde.

[Diable ! j'ai été reconnu ! AD]

Je termine l'exercice n°7 de Ritchie (avec les notations ci-dessus).\\
\\
Dans ce qui suit, $\sideset{}{'} \sum_{a}$ signifie toujours une somme du type $\sum_{a \in \{0,...,p-1\}, \, a+b+c \equiv 0 \pmod p}$. On suppose de plus que $p$ est premier {\it impair}.\\
\\
Au lieu de majorer les caractères par $1$ dans la dernière somme ci-dessus, on développe le produit $(1+\chi_p(a))(1+\chi_p(b))(1+\chi_p(c))$, ce qui donne : $$\mathcal {N} = p^2 + \sum_{b,c=0}^{p-1} \sideset{}{'} \sum_{a} \chi_p(a) + \sum_{a,c=0}^{p-1} \sideset{}{'} \sum_{b} \chi_p(b) + \sum_{a,b=0}^{p-1} \sideset{}{'} \sum_{c} \chi_p(c) + \sum_{c=0}^{p-1} \sideset{}{'} \sum_{a,b} \chi_p(ab) + \sum_{b=0}^{p-1} \sideset{}{'} \sum_{a,c} \chi_p(ac) + \sum_{a=0}^{p-1} \sideset{}{'} \sum_{b,c} \chi_p(bc) + \sideset{}{'} \sum_{a,b,c} \chi_p(abc).$$ Les sommes sont toutes nulles, ça se montre sur le même principe : si $a+b+c = kp$, alors, par périodicité des caractères, on a $\chi_p(a) = \chi_p(-b-c) = \chi_p(-1) \, \chi_p(b+c)$. Prenons l'une des sommes, par exemple : $$S = \sum_{c=0}^{p-1} \sideset{}{'} \sum_{a,b} \chi_p(ab).$$ On a : $$S = \chi_p(-1) p \sum_{c=0}^{p-1} \sum_{b=0}^{p-1} \chi_p(b) \chi_p(b+c),$$ et lorsque $b,c$ varient dans $\{0,...,p-1\}$, $b+c$ a un représentant unique dans cet ensemble, de sorte que : $$S = \chi_p(-1) p \sum_{c=0}^{p-1} \chi_p(c) \sum_{d=0}^{p-1} \chi_p(d) = 0$$ si $p \geqslant 3$.

{\bf Conclusion}. Si $p \geqslant 3$ est premier, alors $\mathcal {N} = p^2$. On vérifie que ce résultat est toujours vrai pour $p=2$.

Borde (message précédent à supprimer. Merci).

Merci, Alain, en général, j'essaie de séparer les phrases, mais, là, je n'ai pu le faire, et, dans ces cas-là, je te laisse les coupures des phrases trop longues, étant incapable de faire cela moi-même en LaTeX...

En supposant que l'exo de Ritchie soit correctement résolu, voici un {\bf exercice n°9}, apparu sur le forum il y a un an (ou plus), mais qui me paraît suffisamment intéressant pour être (re)mis ici :

{\bf Exercice n°9}. {\it Résoudre dans $\(N^{*})^2$ l'équation} : $$5(x+y)^2 = 147 \times \mbox {ppcm}(x,y).$$

Borde.

Bonsoir Borde
<BR>
<BR>Pour les coupures de ligne et autre alignements, Alban a récemment envoyé ce message :
<BR><a href=" http://www.les-mathematiques.net/phorum/read.php?f=2&i=342972&t=342880#reply_342972"&gt; http://www.les-mathematiques.net/phorum/read.php?f=2&i=342972&t=342880#reply_342972</a&gt;
<BR>
<BR>Alain<BR>

Bonjour Borde

Excuse-moi de squater ce fil, mais j'ai corrigé le message d'Alban pour les { } (que la compilation LaTeX a fait disparaitre).
Surtout ces environnement contiennent en eux-même le passage en mode mathématique. Il ne faut surtout pas les encadrer par des $.

Alain

Oui, Alain, j'avais finalement compris...après coup ! Ceci dit, j'essaierai les astuces d'Alban dès que l'occasion s'en présentera.

Voici maintenant un corrigé de l'exercice 6 bis, dont je rappelle l'énoncé : {\it Soit $n \geqslant 2$ entier, et $1=d_1 < d_2 < ... < d_k = n$ les diviseurs de $n$ (et donc $k = \tau(n)$). On note $d_h$ le plus petit diviseur vérifiant $d_h \geqslant \sqrt n$. Montrer que} : $$\sum_{j=1}^{h-1} d_j \leqslant n \ln 2.$$

{\bf Corrigé}.

{\it Etape} 1. On montre que $h = [k/2] + 1$ (où $[t]$ est la partie entière).

En effet, si $k$ est impair, alors $n$ est un carré parfait (résultat classique) et $\sqrt n$ est le diviseur situé au milieu des diviseurs de $n$, et il y a autant de diviseurs $1 < d_2 < ... < d_{h-1}$ que de diviseurs $d_{h+1} < ... < d_k = n$, ce qui donne $h-1 = k-h$, puis $h = [k/2] + 1$. Si $k$ est pair, alors les relations $d_h \, d_{k+1-h} = d_{h-1} \, d_{k+2-h} = n$ et les inégalités $d_{h-1} < \sqrt {n} \leqslant d_h$ impliquent que $d_{k+1-h} \leqslant \sqrt n < d_{k+2-h}$, et donc, par définition de $h$, on a $k+1-h \leqslant h-1$ et $k+2-h \geqslant h$, ce qui entraîne que $h=k/2+1 = [k/2] + 1$.

{\it Etape} 2. L'inégalité $\displaystyle {d_j \leqslant \frac {n}{k+1-j}}$, valable pour tout $j=1,...,k$, donne : $$\sum_{j=1}^{h-1} d_j \leqslant n \sum_{j=k+2-h}^{k} \frac {1}{j}.$$

Si $k$ est pair, alors $k+2-h = k/2 + 1$ est entier et l'inégalité $\displaystyle {\sum_{a < j \leqslant b} \frac {1}{j} \leqslant \ln \left ( \frac{a}{b} \right ) + \frac {1}{2} \left ( \frac {1}{b} - \frac {1}{a} \right ) + \frac {1}{12a^2}}$ fournit : $$\sum_{j=1}^{h-1} d_j \leqslant n \left ( \ln 2 - \frac {3k-2}{6 k^2} \right ) \leqslant n \ln 2.$$

Si $k$ est impair, alors $k \geqslant 3$ (puisque $\tau(n) \geqslant 2$), et on peut poser $k=2m+1$ avec $m \geqslant 1$. On a alors $h=m+1$, et donc : $$\sum_{j=k+2-h}^{k} \frac {1}{j} = \sum_{j=m+2}^{2m+1} \frac {1}{j} \leqslant \ln 2 - \frac {6m^2+4m-1}{12(2m+1)(m+1)^2} \leqslant \ln 2,$$ puisque $m \geqslant 1$.

Borde.

Lire "l'inégalité $\displaystyle {\sum_{a < j \leqslant b} \frac {1}{j} \leqslant \ln \left ( \frac {b}{a} \right ) + \frac {1}{2} \left ( \frac {1}{b} - \frac {1}{a} \right ) + \frac {1}{12a^2}}$..." (au lieu de $\ln(a/b)$).

Merci,

Borde.

Lire : $\leqslant p+1$, au lieu de $\leqslant p$.

Sorry,

Borde.

Correct, Bernard, à toi de jouer...

Borde.

Je reviens un instant sur l'exercice 6 bis montré plus haut : en effet, à y regarder de plus près, il me semble être assez artificiel. Il s'agit d'estimer la somme : $$S_n = \sum_{d \mid n, \, d < \sqrt n} d.$$ On a évidemment : $$S_n \leqslant \sqrt n \sum_{d \mid n} 1 = \sqrt n \times \tau(n),$$ et l'estimation connue $\tau(n) \leqslant 2^{2^{1/\varepsilon}} (e \varepsilon \ln 2)^{-2^{1/\varepsilon}} \, n^{\varepsilon}$, valable pour tout $\varepsilon > 0$, implique que : $$S_n \leqslant 2^{2^{1/\varepsilon}} (e \varepsilon \ln 2)^{-2^{1/\varepsilon}} \, n^{1/2 + \varepsilon},$$ ce qui est quand même nettement meilleur que l'exo 6 bis.

Borde.

Très bien einton, selon ton raisonnement :
Avec $2008 =3.668+2.2$, on obtient :$P_{max}=3^{668}.2^2$

En fait , pour généraliser:
$n \equiv 0,1,3 \pmod 6$, $P_{max}$=3^[n/3]
lire: 3 puissance partie entière de n/3

$n \equiv 2,5 \pmod 6$, $P_{max}$=2.3^[n/3]
lire : 2 x 3 puissance partie entière de n/3

$n \equiv 4 \pmod 6$, $P_{max}$=2^2.3^([n/3]-1)
c'est le cas pour 2008.

AD: désolé, mais trop compliqué en Latex pour moi.

Origine du problème : Le Monde ,énigme de Pierre Berloquin.
La généralisation : bs :-)

Amicalement.

Bonjour,
Exercice 12 : un peu long et technique, je crois me souvenir ( n'ai pas encore remis la main dessus ).
En attendant : entre 0 et 9 : deux solutions : $1,2$

[Merci Alain pour la correction Latex précédente , j'ai compris mon erreur.]
Cordialement.

Bonjour Galax,

En plus, tu sais lire le japonais ?:-) ; si la réponse est non, comment lire ton document en français ou en anglais ? merci.

merci pour la piste concernant l'exo 13.

pour le 12 (suite): pour n compris entre 10 et 99, comme 5!=120, les nombres ne doivent contenir ni 5,6,7,8,9 dans leur écriture;
la quinzaine d'essais à effectuer montrent qu'il n'existe pas de solution entre 10 et 99.

Amicalement.

Bonjour,

Merci Galax, pour ce document en anglais.
Einton, tu as le droit ( ou le devoir ) de proposer un exercice.

Suite de l'exercice 12:
Recherche entre 100 et 999: pas de 8, ni de 9 dans l'écriture; de plus au moins la présence d'un 5 , et au plus
celle d'un 6.
En outre, on remarque que si on effectue le calcul pour 125, le résultat est utilisable pour 152,215,251,512,521.
On commence par 105,106,115,116,...
Résultat : une solution à trois chiffres:
$$145=1! + 4! + 5!$$
Il ne reste plus qu'une solution à trouver , et démontrer pourquoi .
Sincèrement.

Bonsoir,

Exercice 12 : entre 1000 et 9999,
pas de 8 , ni de 9 ; présence de deux, trois ou quatre 6, au plus un 7.
aucune solution dans cete fourchette.
suite et fin en 2006.

Exercice 13: galax , promis, demain je dis le peu que j'ai trouvé.

Amicalement.

Bonjour,
<BR>
<BR>Fin de l'exercice 12:
<BR>
<BR>1)Les deux liens proposés par Galax montrent que ce pb ne possède que 4 solutions: la dernière étant 40585.
<BR>
<BR>2)En remarquant que pour:
<BR><SPAN CLASS="MATH"><IMG WIDTH="125" HEIGHT="34" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/12/31/105889/cv/img1.png&quot; ALT="$ 10^n \leq N <10^{n+1}$"></SPAN>, on doit avoir : <SPAN CLASS="MATH"><IMG WIDTH="65" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/12/31/105889/cv/img2.png&quot; ALT="$ N \leq n.9!$"></SPAN> ,
<BR>il n'est donc pas nécessaire de chercher au-delà de <SPAN CLASS="MATH"><IMG WIDTH="26" HEIGHT="16" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/12/31/105889/cv/img3.png&quot; ALT="$ 10^7$"></SPAN>.
<BR>
<BR>3) les Anglais appellent ces nombres les factorions.
<BR>
<BR>4)La solution détaillée se trouve dans "Mathematics Magazine" , Vol.44, November 1971, pages 278-279; article de George D.Poole.
<BR>(j'avais photocopié cet article , mais ne le retrouve plus, et ne pourrai donc vous le joindre).
<BR>
<BR>5)C'est dans la préface du livre dans lequel Hardy explique sa relation mathématique avec Ramanujan, que Hardy effectue sa remarque sur le peu d'intérêt que présente cet exercice.
<BR>
<BR>Amicalement.<BR>

Salut Galax,

Je ne sais pas si ta méthode se généralise pour cet exercice, mais la "mienne" se généralise sans problème de la façon suivante : notons $a^{*}$ (resp. $b^{*}$) l'inverse de $a \pmod p$ (resp. $b \pmod p$), c'est-à-dire l'unique représentant tel que $aa^{*} \equiv 1 \pmod p$ (resp. $bb^{*} \equiv 1 \pmod p$). Puisque $ax^2 \equiv A \pmod p$ équivaut à $x^2 \equiv a^{*}A \pmod p$, le nombre de solution de l'équation $ax^2 \equiv A \pmod p$ vaut $1 + \chi_p(a^{*}A)$, et même chose avec l'autre, de sorte que le nombre $\mathcal {N}$ de solutions de l'équation $ax^2 + by^2 \equiv 1 \pmod p$ vaut : $$\mathcal {N} = \sum_{A+B=1} (1 + \chi_p(a^{*}A))(1 + \chi_p(b^{*}B).$$ En développant comme je l'ai fait, il reste : $$\mathcal {N} = p + \chi_p(a^{*}b^{*}) J(\chi_p,\chi_p),$$ où, comme précédemment, $J(\chi,\psi)$ est la somme de Jacobi relative aux caractères $\chi$ et $\psi$. Comme $\chi_p = (./p)$ est un caractère {\bf réel}, on a deux choses :

(i) $\chi_p(a^{*}) $ \overline {\chi_p(a)} = \chi_p(a) = (a/p)$ (et même chose pour l'autre),

(ii) $ J(\chi_p,\chi_p) = J(\chi_p,\overline {\chi_p}) = - \chi_p(-1)$.

Il en résulte que : $$\mathcal {N} = p - \chi_p(-ab) = p - \left ( \frac {-ab}{p} \right ).$$

{\bf Remarque}. La condition $p \nmid ab$ est destiné à écarter les cas triviaux $p \mid a$ ou $p \mid b$ dans lesquels $\chi_p(a) = 0$ ou $\chi_p(b) = 0$. Mais si, par exemple, $p \mid a$, ton équation s'écrit en fait $by^2 \equiv 1 \pmod p$. Si $p \mid b$, pas de solution. Si $p \nmid b$, il y a $1 + \chi_p(b^{*}) = 1 + \chi_p(b)$ solutions.

Borde.

Salut Galax,

Je ne sais pas si ta méthode se généralise pour cet exercice, mais la "mienne" se généralise sans problème de la façon suivante : notons $a^{*}$ (resp. $b^{*}$) l'inverse de $a \pmod p$ (resp. $b \pmod p$), c'est-à-dire l'unique représentant tel que $aa^{*} \equiv 1 \pmod p$ (resp. $bb^{*} \equiv 1 \pmod p$). Puisque $ax^2 \equiv A \pmod p$ équivaut à $x^2 \equiv a^{*}A \pmod p$, le nombre de solution de l'équation $ax^2 \equiv A \pmod p$ vaut $1 + \chi_p(a^{*}A)$, et même chose avec l'autre, de sorte que le nombre $\mathcal {N}$ de solutions de l'équation $ax^2 + by^2 \equiv 1 \pmod p$ vaut : $$\mathcal {N} = \sum_{A+B=1} (1 + \chi_p(a^{*}A))(1 + \chi_p(b^{*}B).$$ En développant comme je l'ai fait, il reste : $$\mathcal {N} = p + \chi_p(a^{*}b^{*}) J(\chi_p,\chi_p),$$ où, comme précédemment, $J(\chi,\psi)$ est la somme de Jacobi relative aux caractères $\chi$ et $\psi$. Comme $\chi_p = (./p)$ est un caractère {\bf réel}, on a deux choses :

(i) $\chi_p(a^{*}) = \overline {\chi_p(a)} = \chi_p(a) = (a/p)$ (et même chose pour l'autre),

(ii) $ J(\chi_p,\chi_p) = J(\chi_p,\overline {\chi_p}) = - \chi_p(-1)$.

Il en résulte que : $$\mathcal {N} = p - \chi_p(-ab) = p - \left ( \frac {-ab}{p} \right ).$$

{\bf Remarque}. La condition $p \nmid ab$ est destiné à écarter les cas triviaux $p \mid a$ ou $p \mid b$ dans lesquels $\chi_p(a) = 0$ ou $\chi_p(b) = 0$. Mais si, par exemple, $p \mid a$, ton équation s'écrit en fait $by^2 \equiv 1 \pmod p$. Si $p \mid b$, pas de solution. Si $p \nmid b$, il y a $1 + \chi_p(b^{*}) = 1 + \chi_p(b)$ solutions.

Borde.

$2^{35\times 11}+1=2^{385}+1 = \allowbreak 7\,88040\,12392\,78895\,84245\,58080\,20028\,72276\,10159\,47854\,09308\,93335\,89658\,68084\,91443\,54299$
$\qquad\qquad\qquad\qquad\qquad 44212\,22828\,53250\,97698\,31281\,61325\,59806\,13633$