Suite périodique, pgcd et ppcm

[Al-Kashi]

Bonjour à tous,

Soit et deux suites d'entiers naturels tels que . Pour tout :



Montrer que la suite est périodique à partir d'un certain rang.
-------------------------
Si et sont premiers entre eux, la conclusion est immédiate.
Si et ne sont pas premiers entre eux, alors là je tourne en rond
Merci d'avance pour toutes vos indications.

[Ben314]

Salut,
En vrac :

Si et ne sont pas premiers entre eux, alors là je tourne en rond

Vu que le but est de montrer que c'est périodique, de "tourner en rond", c'est plutôt bon signe... (humour...)

Soit et deux suites de nombres réels tels que .

Ca serait pas plutôt des entiers (naturels) ?

Si et sont premiers entre eux, la conclusion est immédiate.

Ben.... perso, je vois pas bien pourquoi...

Sinon, après avoir trouvé que ton truc était bien rigolo et que je voyais pas du tout par quel bout partir, j'ai fini par faire un essai en partant de et et... c'est pas du tout périodique : on obtient et pour tout .

Ou alors j'ai mal lu (ou compris) l'énoncé...

EDIT : j'ai effectivement mal lu l'énoncé : il faut uniquement montrer que la suite est périodique et pas les deux...

[Al-Kashi]

Effectivement, il s'agit d'une suite d'entiers naturels.
J'ai écrit un petit programme pour illustrer la situation, la suite est périodique à partir d'un certain rang qui dépend de et .

[Ben314]

Bon, ben je suis complètement sec.
Même dans ce cas là

Si et sont premiers entre eux, la conclusion est immédiate.

je vois pas grand chose : en partant de 11 et 229 par exemple, ça met quand même un petit moment à se stabiliser sur 2,3,4,5,2,3,4,5,....

[Al-Kashi]

Tu as raison, ce n'est pas aussi évident que je le pensais.
Je me suis trompé dans mon raisonnement. Du coup, il y a tout à refaire

[zygomatique]

salut

une idée ...

et avec pgcd (u, v) = 1

et

au rang suivant :

1/ uv + 1 et uv sont consécutifs donc sont premiers entre eux

2/ soit divise uv + 1 et alors

et

3/ soit ne divise pas uv + 1 et alors est un diviseur de et et

sachant que divise uv + 1 ...


mais bon où va-t-on aller comme ça ...

peut-être cela inspirera quelqu'un ....


EDIT : msg corrigé suite à la remarque de Ben314 ... et ma grossière erreur ...

[Ben314]

et avec pgcd (u, v) = 1
et

Il me semble bien que, si alors et pas
Mais bon, ça change pas grand chose à la suite : si on fait "apparaitre" à la place de ton ça donne comme reste qui est "presque" le même que ton .

[nodgim]

Je crois que j'ai la solution, mais une âme charitable est nécessaire pour débrouiller mon charabia...

Il faut montrer que la suite des " an ", si elle croît assez longtemps pour obtenir ak >= 2 * a0, alors on aboutira forcément à un couple (a, b ) premiers entre eux. Car si on n'atteint pas ce double 2 * a0, le pgcd sera moindre que le pgcd origine ( la fraction maximale étant la moitié ).
Quand la suite des " an " croît, mettons par convention depuis ak, ( incrémentation d'une unité à chaque pas) alors la suite des " bn " décroît d'une unité ( puisque dans ce cas bn = k an) à chaque pas.
La suite décroissante des "bn" a une suite croissante de diviseurs : ak, ak+1, ak+2, ...ak + j
Si ak + j dépasse ou atteint 2 *ak, alors on sait que b (k-1) est divisible par a( k-1), b(k-2) par a(k-2) et ainsi de suite jusqu'a a = 1. Dans ce cas, toutes les valeurs de " a " au delà de 2 * ak divisent le b correspondant, tant que " a " n'est pas un nombre premier. Car les nombres composés de la suite des entiers naturels se déduisent du séquencement des nombres premiers qui le composent. Or, quand " a " dépassera b/2, le premier nombre premier atteint par a ne divisera pas b.

[Al-Kashi]

Il faudrait qu'on demande à Erdos ou Polya pour nous donner un coup de main .

[Ben314]

Il me semble bien qu'effectivement si on montre que, à chaque fois que la suite se met à monter, elle ne va pas plus haut que le double de la valeur de départ (où elle a commencé à monter), alors ça montrera bien quelle est bornée vu que quand elle diminue, c'est au minimum en étant divisée par 2.
Mais par contre, dans l'absolu, c'est faux : on peut tout à fait trouver une suite telle que a1=2 puis qui monte aussi haut qu'on veut et il y a même des suites dont la période est 2,3,4,5,2,3,4,5,... donc qui, partant de 2 montent jusqu'à 5 à chaque fois.

Sinon, concernant ta "suite décroissant de bn qui sont des diviseurs de ak, ak+1, ak+2,..." il y a unr façon nettement plus simple de l'exprimer vu que de dire que ak+j divise bk-j pour tout j entre ? et ?, ça équivaut complètement à dire que ak+j divise ak+bk pour tout j entre ? et ? avec l'énorme intérêt que ak+bk ne dépend pas de j.

Par exemple, si tu veut une suite qui, partant de a=2 et b=?, monte pendant un bon bout de temps, il faut que tu prenne b tel que b+2 soit divisible par 2,3,4,5,6,7,....
Par exemple avec b = 16x9x5x7x11x13 - 2 = 720718 (et a=2), ça va pas mal monter au début.

[nodgim]

Attention, Ben. Je n'ai pas écrit qu'une suite de " a " ne pouvait pas monter plus haut que jusqu'à " 2a " . J'ai juste écrit que si tel était le cas, la croissance s'arrête sur un " a " premier, et donc donne (a, b) premier. Mais bon, j'ai pu me planter.

[Ben314]

Non, c'est moi qui avait mal compris.
L'idée me semble pas mauvaise du tout, et j'ai bien l'impression que ça marche... presque... :
Partant de (a,b) quelconque, il est évidement qu'on ne peut pas faire (+1,-1) ad vitam aeternam.
Et si on fait (+1,-1) exactement m-1 fois mais pas la m-ième fois, ça signifie précisément que a+b est divisible par a, a+1 , a+2 , . . . , a+m-1 mais qu'il n'est pas divisible par a+m.
Donc la divisibilité par a+1 , a+2 , . . . , a+m-1 n'entraine pas mécaniquement celle par a+m.
Là, effectivement on se dit que, si m est "un peu grand", ça doit signifier qu'en fait a+m est premier, mais ce n'est pas tout à fait vrai : a+m peut aussi être une puissance d'un nombre premier.
Par exemple, le fait qu'un entier donné soit divisible par 2, par 3, par 4,..., par 31 n'implique pas qu'il est divisible par 32=2^5.

Mais y'a peut-être quand même quelque chose à en tirer : j'ai bien l'impression que, en supposant m "un peu grand", on doit pouvoir en déduire que a+m est une puissance d'un nombre premier, mais d'un autre coté, c'est pas franchement le même résultat qu'on obtient vu que si a+m=2^k, alors à l'étape suivante il n'y aura qu'une simple division par 2 et pas une redescente sur a=2 comme dans le cas a+m premier...

[Al-Kashi]

Bonsoir à tous,
Ci-joint une solution parmi d'autres possibles. Elle m'a été envoyée par un ami qui m'a dit que l'exercice a été posé aux IMO (Olympiades internationales).

[Ben314]

C'est effectivement très joli et... pas bien facile à trouver... (le principe des olympiades quoi)

...si on fait (+1,-1) exactement m-1 fois mais pas la m-ième fois, ça signifie précisément que a+b est divisible par a, a+1 , a+2 , . . . , a+m-1 mais qu'il n'est pas divisible par a+m....

En fait c'est là que j'ai franchement manqué d'inspiration : arrivé à ce point on peut tout à fait écrire que :
Il est donc parfaitement naturel de considérer le plus petit entier supérieur ou égal à qui ne divise pas ...

Impardonnable...

[Al-Kashi]

Tu as fait un bon boulot , mais l'exercice n'était pas évident.

[Ben314]

Au cas où certains n'aiment pas trop l'Anglais, en Français, ça donne ça :

Dans la suite des , on s'intéresse aux "sommets", c'est à dire aux couples tels que c'est à dire en fait aux couples tels que .
Partant d'un tel couple, et en allant jusqu'au "sommet" suivant, on obtient la suite :

("sommet" suivant)
Ce qui signifie que divisent mais que
Or et ne divise pas donc ne divise pas non plus ce qui signifie qu'il ne fait pas parti de la séquence et donc que .
La suite des "sommets" est donc décroissante (au sens large) et comme c'est une suite d'entier naturels, elle est stationnaire à partir d'un certain rang ce qui signifie qu'à partir d'un certain rang, toutes les suites de "sommet" à "sommet" sont du type çi dessus avec toujours le même et avec ("sommet" suivant) donc .
Enfin, le terme suivant sera avec
Ce qui montre que, à partir d'un certain rang, toutes les suites de "sommet" à "sommet" auront non seulement le "même " mais aussi le "même " d'où la périodicité.

Et nodgim était pas si loin du compte que ça, sauf que la constatation à faire, c'était pas qu'au "sommet" suivant on tombe (dans certains cas) sur un nombre premier, mais qu'au "sommet" suivant, on tombe systématiquement sur un entier inférieur au "sommet" précédent...

[Al-Kashi]

Merci pour la traduction ça aidera certainement beaucoup de monde.
J'ai eu une 2ème méthode un peu plus longue que je posterai ce soir .
Bonne journée.

[nodgim]

@ Ben: tu es bien indulgent pour ce que j'ai fait, certes il y avait bien le fil, mais le déclic pour l'invariant d+m n'était pas là (bien que cette idée d'invariant me trottinait, mais je ne l'ai pas vue).
Je ne pensais pas que la solution pouvait être aussi courte.
Les auteurs de ces énoncés sont des Machiavels.

[zygomatique]

à noter les cas particuliers (2, 4) où a dépasse b

et (2, 5) et ce que fait la suite b dans ce dernier cas ...

[Ben314]

Sinon, si je me suis pas trop gouré, en fait des périodes possibles, il n'y en a que 4 :
2 -> 2 -> 2 . . .
2 -> 3 -> 2 -> 3 -> 2-> 3 . . .
3 -> 4 -> 3 -> 4 -> 3 -> 4 . . .
2 -> 3 -> 4 -> 5 -> 2 -> 3 -> 4 -> 5 -> . . .