Un carré chiffré - solution

Un carré parfait de 8 chiffres, la moitié de droite est un de plus que la moitié de gauche.

Echauffement

On va commencer avec le nombre de deux chiffres...
N² = 10a + b, b = a + 1 soit N² = 11*a + 1
Le problème revient à trouver un nombre N tel que N² ≡ 1 modulo 11
Mais comme 11 est un nombre premier, seuls 1 et -1 ≡ 10 modulo 11 sont solutions de cette équation.
Comme on veut 10 ≤ N² ≤ 99 soit 3 < N < 10 il n'y a aucune solution.
Bon la théorie c'est bien beau mais ici les carrés de 2 chiffres on les connaît, et on "voit" de suite qu'il n'y a pas de solution...

Passons à 4 chiffres
Il faut résoudre de même N² = 100a + b, b = a + 1 soit N² = 101*a + 1,
soit N² ≡ 1 modulo 101
Pour la même raison (101 premier) les seules solutions sont N = 1 et 100, aucune n'est dans les limites
1000 ≤ N² ≤ 9999, 31<N<100
C'était déja moins évident (essayer les 68 carrés candidats ???).

Et maintenant du sérieux...

Un peu plus de chance avec 6 chiffres ?
Là ce n'est même pas la peine d'essayer brutalement les 683 carrés de 6 chiffres ...
Mais on a l'habitude... N² ≡ 1 modulo 1001 et 316 < N < 1000
Ah, ça va devenir intéressant ! 1001 = 7 * 11 * 13 n'est plus premier !
N² ≡ 1 modulo 1001 est équivallent à N² ≡ 1 modulo 7 et N² ≡ 1 modulo 11 et N² ≡ 1 modulo 13
Cela donne N ≡ ± 1 modulo 7 et N ≡ ± 1 modulo 11 et N ≡ ± 1 modulo 13.
Encore un coup des restes chinois... L'application de ce théorème est indispensable ici.
Certes si on choisit tous les signes égaux, on peut simplifier en N ≡ ± 1 modulo 1001, qui ne donne pas de solution.
Mais on peut aussi choisir des signes différent pour chaque congruence, il reste 6 combinaisons de signes non tous égaux et donc 6 solutions non triviales. Reste à les calculer.

Les calculs du théorème des restes chinois donnent :
N ≡ a mod 7 ≡ b mod 11 ≡ c mod 13
(11*13) ^-1 ≡ 3 ^-1 ≡ 5 mod 7
(7*13) ^-1 ≡ 3 ^-1 ≡ 4 mod 11
(7*11) ^-1 ≡ 12 ^-1 ≡ 12 mod 13

N ≡ 5*11*13*a + 4*7*13*b + 12*7*11*c modulo 1001
Avec toutes les combinaisons de a,b,c = ±1

N ≡ 5*11*13 + 4*7*13 + 12*7*11 ≡ 1 mod 1001, ce que l'on savait déja
N ≡ 5*11*13 + 4*7*13 - 12*7*11 ≡ 155 mod 1001
N ≡ 5*11*13 - 4*7*13 + 12*7*11 ≡ 274 mod 1001
N ≡ 5*11*13 - 4*7*13 - 12*7*11 ≡ 428 mod 1001
Et les opposés :
N ≡ - 1, - 155, - 274, - 428 mod 1001 soit 1000, 846, 727 et 573

Les seules valeurs avec 316 < N < 1000 sont N = 428, 573, 727, 846
Il y a donc 4 solutions :
428² = 183184, 573² = 328329, 727² = 528529 et 846² = 715716

La touche "mod" fume...

La même méthode appliquée à 8 chiffres donne N² ≡ 1 modulo 10001 et comme 10001 = 73 x 137, un petit coup de restes chinois :
73 ^-1 ≡ 122 modulo 137
137 ^-1 ≡ 8 modulo 73
et N ≡ ± 122*73 ± 8*137 modulo 10001
Le seul candidat sérieux (±1 est exclus) étant N ≡ 122*73 - 8*137 = 7810 modulo 10001 et son opposé -7810 ≡ 2191
Dans la fourchette 3162 < N < 10000, la seule solution est
7810² = 60996100

Avec 10 chiffres N² ≡ 1 modulo 100001 et 100001 = 11 x 9091
11 ^-1 ≡ 1653 modulo 9091
9091 ^-1 ≡ 5 ^-1 ≡ 9 modulo 11
N ≡ ± (1653*11 - 9*9091) = 63636 et 36365 modulo 100001
31622 < N < 100000, les deux solutions sont valables :
36365² = 1322413225 et 63636² = 4049540496

Puis 12 chiffres, la maison ne recule devant rien ! 1000001 = 101 x 9901
101 ^-1 ≡ 6568 modulo 9901
9901 ^-1 ≡ 34 modulo 101
N ≡ ± (6568*101 - 34*9901) = 326734 et 673267 modulo 1000001
316227 < N < 1000000 et les deux solutions :
326734² = 106755106756 et 673267² = 453288453289

Et même tant qu'à faire 14 chiffres : 10000001 = 11 x 909091
11 ^-1 ≡ 247934 modulo 909091
909091 ^-1 ≡ 8 modulo 11
N ≡ ± (247934*11 - 8*909091) = 4545454 et 5454547 modulo 10000001
3162277 < N < 10000000
4545454² = 20661152066116 et 5454547² = 29752082975209
Joli le 4545454 !

Pour aller plus loin, voir les décompositions en facteurs premiers de 10ⁿ + 1
A noter que les seuls nombres premiers connus de cette forme sont 11 et 101, il y a donc toutes chances qu'il y ait des solutions pour tout n à notre problème...

 

(vous avez vu comment je calcule 137 ^-1 ≡ 8 modulo 73 ? même pas mal ! résoudre simplement 137x + 73y = 1 ...
Algorithme d'Euclide, c'est tout programmé là)