Forum de mathématiques - Bibm@th.net

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 511

arithmétique toujours ou plutôt scout toujours?

Bonjour,

J'ai eu (pas mal à vrai dire) de fil à retordre sur un sujet curieux d'arithmétique, nanti juste de ces indications:

Je suis un peu dur, je les masque alors que j'ai pu en profiter, mais certains parmi vous préfèreront peut-être chercher carrément à partir de zéro:

▼méthode XXXXXXXXXXXXX

- Envisager une récurrence sur n
- si p est un diviseur premier de n, distinguer les cas p et a premiers entre eux, du cas contraire.
- on pourra utiliser le théorème chinois

Et ... l'énoncé, dont seule la brièveté le dispute à l'étrangeté et la beauté :

Montrer que si a et n sont des entiers naturels non nuls, la suite $a^{a^{a^{.....}}}$ est toujours stationnaire modulo n.
Ainsi les premiers termes sont $ a , a^a , a^{a^a}, a^{a^{a^a}} $ ...  . Modulo 12 par exemple, cette suite n'évoluera plus à moment donné.

J'indiquerai ma démarche si certains s'y intéressent (en espérant que ce soit juste -je croise les doigts :-) , et pas à la scout!! ).
Vous aurez sans doute trouvé avant.

Nota bene:

  Pour faciliter l'écriture , un certain Mr  Knuth  a proposé une notation simplificatrice $a \uparrow \uparrow b$  signifiant que a apparait (b) fois dans l'expression. Il ne s'est pas arrêté là proposant ensuite l'opérateur triple flèche , puis quadruple flèche et ainsi de suite.
par exemple $ a \uparrow \uparrow \uparrow 3 =  a \uparrow \uparrow a \uparrow \uparrow a $ ( associer depuis la droite).

Je vous encourage à noter avec ce procédé vos recherches/écrits, pour ne pas acheter des dizaines de cahiers à l'Intermarché (ou plutôt au Mamouth ) près de chez vous... car les nombres explosent .

On doit trouver en ligne des calculettes modulo x si on veut faire des essais rapides en faisant varier a et n: je n'ai pas cherché.

j'ai corrigé in extremis  l'intitulé de l'aide masquée, qui allait vous en dire trop. Où serait le plaisir?

$ 3 \uparrow \uparrow 4 = 3^{3^{3^{3}}} $  est de la forme 12580...39387 et a 3 638 334 640 025  chiffres ( pour donner une idée !).[ valeurs wikipedia ]

Remarque de dernière minute:

J'ai tenté a avec la valeur 3,  afin de visualiser dans quelques  cas de n la stationnarité mais et ça explose les calculs, pour des valeurs de n qui ne sont pas trop particulières bien-sûr.

Il reste donc l'arithmétique pure... pour s'en convaincre.

Bon courage
Alain

Dernière modification par bridgslam (10-08-2024 17:37:41)

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 511

Re : arithmétique toujours ou plutôt scout toujours?

Bonjour,

Je vous rédige finalement mon draft, m'étant auto-persuadé de le faire dans les cas extrêmes que la question aura  suscités ( intérêt débordant, ou au contraire quasi-nul, cette éventualité semblant prédominer ..., un sursaut pouvant surgir alors compte-tenu de sa lecture).
Je cache néanmoins le texte, au cas où la curiosité de la recherche vous titillerait encore.

J' utiliserai la notation de Donald Knuth, sur laquelle j'étais tombée à contre-coup sur Wikipedia, pour limiter la lourdeur des expressions des puissances itérées.

▼une idée

J 'utiliserai la récurrence forte sur le modulo N, on verra dans la suite que c'est important vis à vis du  "noyau dur" de la preuve.
a est donné, je note la suite $u$  telle que $u_k = a \uparrow \uparrow k$

Cas N=1:  1 divisant tout entier, la stationnarité est manifeste dès le départ de la suite

Soit N au moins égal à 2, supposons la propriété vrai jusqu'au rang N-1. On doit montrer sa véracité au rang N.
Notations:
$N = \prod_{p \;\;premier} p^{\alpha} $ (je zappe les indices pour simplifier) .

L'utilisation du théorème chinois donnera ipso facto le résultat si on prouve la propriété sur chaque facteur $ p^{\alpha}$ de N puisque en prenant le max M des rangs à partir desquels la suite u est stationnaire modulo ces facteurs, la suite sera évidemment stationnaire avec les restes chinois à partir de M modulo le produit N des $ p^{\alpha}$

Donc soit p premier un diviseur de N, et $v_p(N) = \alpha$ sa valuation sur p.
Deux cas:
1- 
  p divise a. Si $ \alpha = 1 $ c'est immédiat, sinon un calcul facile montre, puisque la stationnarité est vraie au rang $p^{\alpha - 1}$ selon l'hypothèse de récurrence, en utilisant que pour tout entier non nul $\beta$ on a l'inégalité $ \beta \le p^{\beta} - 1$ , qui induit la propriété de stationnarité (à 0) au rang $p^{\alpha}$ simplement.

2- p et a sont premiers entre eux. (c'est la situation qui m'a laissé pantois un moment...)
Mais alors a et $p^{\alpha}$ sont étrangers. Appliquons alors l'hypothèse de récurrence au rang $\phi( p^{\alpha} )$ (indicatrice d'Euler, "méthode indicatrice", j'ai pensé que ça pouvait donner trop d'indices, j'ai alors modifié en "méthode indicative" puis en rien du tout au final d'où les croix).
Ce rang étant strictement inférieur à N:
$ \exists b : c \ge b => a \uparrow \uparrow c \equiv a  \uparrow \uparrow (c-1) \mod \phi( p^{\alpha} )$.
A partir de $b$ les congruences sont fixes modulo $\phi(p^{\alpha})$

Alors si $c \ge b$ $a^{a \uparrow \uparrow c} =  a \uparrow \uparrow ( c+1) = (a \uparrow \uparrow c) a^{\lambda  \phi( p^{\alpha} )} $

Il est clair que l'on retombe sur nos pieds avec le théorème d'Euler $(a^{\phi( p^{\alpha})})^{\lambda} \equiv 1^{\lambda} \equiv 1 \mod p^{\alpha} $ , ce qui donne la propriété de stationnarité au rang espéré $p^{\alpha} $ à partir de $b+1$.

Noter un petit piège: l'égalité de congruence ne se transmet pas automatiquement par l'opération de mise en puissance (à modulo fixe),
Si deux termes successifs de u sont dans la même classe modulo N, rien ne dit que cela se poursuit ensuite .
$u_k \equiv u_{k+1}$ ne se transmet pas en se décalant d'un rang sur $k$ en général. D'où l'arsenal assez lourd de cette preuve: récurrence forte+des modulo bien choisis pour voyager de stationnarité en stationnarité...

Si on prend comme essai a= 3, N=5 les choses se "dévissent" ainsi au cours du voyage "modulo":

Pour modulo 2= $\phi(4)$  : la suite est stationnaire d'emblée (classe 1 modulo 2), puis stationnaire modulo 4 = $\phi(5)$ à partir de l'indice 2 (classe 3 modulo 4),
enfin à partir de l'indice 3 c'est stationnaire à 2 modulo 5.
Ma calculette a coincé à partir de $3 \uparrow \uparrow 4 = 3^{3^{27}} $... qui est $3^{7\;625\;597\;484\;987}$ mais c'était déjà un petit miracle qu'elle tienne le coup jusque là :-).

Je n'ai pas regardé le point de vue algorithmique qui permettrait d'évaluer ( même de façon approchée) vers quel rang ça converge.
Un programme qui suit les dévissages/vissages puis conclut avec le théorème chinois est sans doute possible pour trouver la valeur de convergence dans tous les cas, il doit être probablement assez pénible à écrire.

Bon dimanche, ici le temps s'arrange
Alain

Dernière modification par bridgslam (15-08-2024 16:58:59)

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."