Défi - Arithmétique

[upium666]

Bonjour à tous et à toutes !

Trouver le nombre de couples d'entiers naturels tels que :


Bon courage !

[Cliffe]

?

?

[Ben314]

Je pense que les sont en fait des ("divise")

[Cliffe]

ça ressemble à une division

[chan79]

ça ressemble à une division

c'est pour les solutions du genre (10,99) ?
99 divise (10²-1)
10 divise (99²-1)

[upium666]

Je pense que les sont en fait des ("divise")

Oui oui, ce sont des "divise"

[beagle]

ben déjà il y a les n et (n+1)
n divise (n+1)²-1
et (n+1) divise aussi n²-1

donc si 10+1 = 99 est faux c'est qu'il y a d'autres solutions!

[beagle]

par contre si 10 et 10²-1 marchent
ben
et si
n et n²-1 marchait?
n²-1 moins que 100

[Tiruxa]

Ma fois oui n et n²-1 avec n²-1 inférieur à 100 conviennent
en effet (n²-1)²-1 = n^4-2n²=n(n^3-2n) c'est bien un multiple de n

[Monsieur23]

# let bar = let f= ref 0 in
# for i=1 to 100 do
# for j=1 to 100 do
# if ( (j*j - 1) mod i == 0 && (i*i - 1) mod j == 0)
# then (f := !f+1)
# done; done; !f;;
val bar : int = 417




Edit : Ah, j'avais pas vu le n<m…

Code: Tout sélectionner

# let bar = let f= ref 0 in
# for i=1 to 100 do
#    for j=1 to (i-1) do
#         if ( (j*j - 1) mod i == 0 && (i*i - 1) mod j == 0)
#          then begin (f := !f+1); print_newline (); print_char '('; print_int j; print_char ';'; print_int i; print_char ')' end
# done; done; !f;;

(1;2)
(1;3)
(2;3)
(1;4)
(3;4)
(1;5)
(4;5)
(1;6)
(5;6)
(1;7)
(6;7)
(1;8)
(3;8)
(7;8)
(1;9)
(8;9)
(1;10)
(9;10)
(1;11)
(10;11)
(1;12)
(11;12)
(1;13)
(12;13)
(1;14)
(13;14)
(1;15)
(4;15)
(14;15)
(1;16)
(15;16)
(1;17)
(16;17)
(1;18)
(17;18)
(1;19)
(18;19)
(1;20)
(19;20)
(1;21)
(8;21)
(20;21)
(1;22)
(21;22)
(1;23)
(22;23)
(1;24)
(5;24)
(23;24)
(1;25)
(24;25)
(1;26)
(25;26)
(1;27)
(26;27)
(1;28)
(27;28)
(1;29)
(28;29)
(1;30)
(29;30)
(1;31)
(30;31)
(1;32)
(31;32)
(1;33)
(32;33)
(1;34)
(33;34)
(1;35)
(6;35)
(34;35)
(1;36)
(35;36)
(1;37)
(36;37)
(1;38)
(37;38)
(1;39)
(38;39)
(1;40)
(39;40)
(1;41)
(40;41)
(1;42)
(41;42)
(1;43)
(42;43)
(1;44)
(43;44)
(1;45)
(44;45)
(1;46)
(45;46)
(1;47)
(46;47)
(1;48)
(7;48)
(47;48)
(1;49)
(48;49)
(1;50)
(49;50)
(1;51)
(50;51)
(1;52)
(51;52)
(1;53)
(52;53)
(1;54)
(53;54)
(1;55)
(21;55)
(54;55)
(1;56)
(15;56)
(55;56)
(1;57)
(56;57)
(1;58)
(57;58)
(1;59)
(58;59)
(1;60)
(59;60)
(1;61)
(60;61)
(1;62)
(61;62)
(1;63)
(8;63)
(62;63)
(1;64)
(63;64)
(1;65)
(64;65)
(1;66)
(65;66)
(1;67)
(66;67)
(1;68)
(67;68)
(1;69)
(68;69)
(1;70)
(69;70)
(1;71)
(70;71)
(1;72)
(71;72)
(1;73)
(72;73)
(1;74)
(73;74)
(1;75)
(74;75)
(1;76)
(75;76)
(1;77)
(76;77)
(1;78)
(77;78)
(1;79)
(78;79)
(1;80)
(9;80)
(79;80)
(1;81)
(80;81)
(1;82)
(81;82)
(1;83)
(82;83)
(1;84)
(83;84)
(1;85)
(84;85)
(1;86)
(85;86)
(1;87)
(86;87)
(1;88)
(87;88)
(1;89)
(88;89)
(1;90)
(89;90)
(1;91)
(90;91)
(1;92)
(91;92)
(1;93)
(92;93)
(1;94)
(93;94)
(1;95)
(94;95)
(1;96)
(95;96)
(1;97)
(96;97)
(1;98)
(97;98)
(1;99)
(10;99)
(98;99)
(1;100)
(99;100)val bar : int = 208

[Ben314]

Vu la tête des solution, je pense que ça serait pas mal d'éliminer les solutions "triviales" n=1 et n=m-1 (l'énoncé élimine les cas n=1 mais pas le deuxième)

[Ben314]

J'ai l'impression qu'on peut quand même faire un peu de théorie (descente de Fermat...)

Soit ) : solution "de base"
Soit donc est de nouveau dans et en réitérant le processus, on finira par tomber sur une solution "de base" (car )

Conclusion : on obtient toutes les solutions en partant des solutions "de base" et en itérant le processus à l'envers, c'est à dire en passant de la solution avec à la solution avec

Par exemple :

[upium666]

J'ai l'impression qu'on peut quand même faire un peu de théorie (descente de Fermat...)

Soit ) : solution "de base"
Soit donc est de nouveau dans et en réitérant le processus, on finira par tomber sur une solution "de base" (car )

Conclusion : on obtient toutes les solutions en partant des solutions "de base" et en itérant le processus à l'envers, c'est à dire en passant de la solution avec à la solution avec

Peut-on dénombrer les solutions alors ?
C'est le but de l'exercice

[chan79]

Peut-on dénombrer les solutions alors ?
C'est le but de l'exercice

Comme l'a indiqué Monsieur23, il y en a 208.
Ci-dessous les 11 solutions non triviales:

[beagle]

pas le temps,
certains non triviaux ressemblent à des
n, k(n-1)
le 15,56
le 8,21

faut voir si k(n+1) marche

je suis à la bourre,a+

[beagle]

certains sont des:
n, (n+1)(n-1)
3,2x4
4,3x5
5,4x6
6,5x7
7,6x8
8, 7x9
9,8x10
10,9x11

[beagle]

ensuite le:
3x5, (3x5-1)(3x5+1) qui est un peu gros, dépassant 100 a été rabotté
en
3x5, (3x5-1) racine carrée de 16

le 8, 7x9
ben il se transforme en
8,7xracine carrée de 9
8,21

[Tiruxa]

Peut-on dénombrer les solutions alors ?
C'est le but de l'exercice

Avec l'excellente contribution de Ben 314 cela me semble clair :

du type (n;n+1) avec n variant de 1 à 99 il y a 99 solutions

du type (1;n) avec n variant de 3 à 100, il y en a 98

du type (n;n²-1) avec n variant de 3 à 10, il y en a 8

soit déjà un total de 205

Les 3 dernières sont (8;21) et (15;56) du type (n²-1;n(n²-2))
et enfin (21;55) du type (n(n²-2);n^4-3n²+1)

Donc il y en a bien 208.

Ps: les valeurs de n sont choisies pour rester dans l'intervalle et pour ne pas reprendre un couple du type (n;n+1) déjà compté.

[Ben314]

Résumé de l'épisode précédent :
Les solutions sont trés exactement les couples avec :
; (entier quelconque >1) ;

Episode du jour :
En fait,
Par récurrence sur n
- Amorce :

- Hérédité : si alors



Le polynôme caractéristique associé à cette récurrence linéaire est de discriminant
- Si il admet une seule racine double donc puis ; donnent ce qui donne tout les couples comme solutions au problème de départ.
- Si les racines sont et puis ; donnent

Avec la valeur explicite de on peut facilement calculer le nombres de termes de la suite qui sont inférieurs à une constante fixé (surtout que donc il ne "compte pas"...) et en déduire le nombre de solutions du problème de départ (il faut quand même sommer sur les différentes valeurs possibles de a...)

Edit : un truc rogolo, c'est que la suite correspondant à a=3 donc commençant par 1,3 et vérifiant la formule de récurrence , en fait (suite de Fibonacci)
De même, si alors ( est divisible par )
De même, si alors ( est divisible par )
etc...