Un problème assez compliqué, inspiré d'un des problèmes mensuels du site diophante.fr (en plus dur, histoire d'ajouter des choses ^^)
Soit k un entier strictement positif, soit n un entier strictement positif tel que n*k+1 et n*(k+1)+1 sont tous deux des carrés.
1) Quels sont les derniers chiffres du plus petit n possible, écrit en binaire, pour tout k ? (Je ne précise pas combien de chiffres, c'est vous qui verrez)
2) Prenons un nombre : nous sommes le 21/12/2011 et il est 14h00, on va prendre 211220111400. Pour quelle valeur de k le plus petit n possible est-il 211220111400?
3) Montrer enfin que pour tout k, la plus petite valeur de n divise toutes les autres.
4) Question Bonus
Trouver une formule TRES simple qui lie k ainsi que 3 valeurs successives de n
La case valide la réponse 2
Indices:
Spoiler : [Afficher le message] Si on note nos deux carrés a² et b², il est possible d'écrire une équation qui lie a, b et k. Commencez par trouver cette équation.
Spoiler : [Afficher le message] (k+1)a² = k(k+1)n + (k+1) = kb² + 1; donc (k+1)a²-kb² = 1
C'est une équation diophantienne du second degré ça
Spoiler : [Afficher le message]
Comment résoudre une équation de type X² - aY² = b ?
On appellera "triplet valide" un triplet (x,y,z) tel que x²-ay² = z. Si (x0, y0, z0) et (x1, y1, z1) sont 2 triplets valides, alors (x0*x1 + a*y0*y1, x0*y1+x1*y0, z0*z1) en est un aussi.
La preuve: (x0*x1+a*y0*y1)² -a(x0*y1+x1*y0)² =
x0²x1² + 2a*x0*y0*x1*y1+a²y0²y1² -ax0²y1² -2a*x0*y0*x1*y1 -ax1²y0² =
x0²x1² + a²y0²y1² - ax0²y1² - ax1²y0² =
x0² ( x1² -ay1²) - a*y0² (x1²-ay1²) =
(x1²-ay1²)(x0²-ay0²) = z1*z0
Par conséquent, si on cherche à résoudre X² - aY² = b, en ayant un triplet (Xi, Yi, b) et un triplet (Xg, Yg, 1); on pourrait générer une infinité de triplets de manière récursive: le premier serait par exemple (Xi*XG+a*Yi*Yg, Yi*Xg+Xi*Yg, b). Autrement dit, les 2 premiers nombres de notre triplet seraient des valeurs X et Y solutions de notre équation.
On peut aussi montrer (c'est plus complexe) que toutes les solutions possibles sont bien générées ainsi.
Pour résumer, si je cherche à résoudre X²-aY²=b:
- je cherche une solution initiale (Xi, Yi)
- je cherche une solution générale (Xg, Yg) à l'équation X²-aY² = 1
- je génère tous les (Xn, Yn), la solution suivante étant à chaque fois (Xn.Xg+aYn.Yg, Yn.Xg+Xn.Yg)
Accueil
