Une question d'arithmétique difficile

**KerLannais** · 21/04/2009, 14h30

bonjour,

Je propose à ceux qui sont intéressés une petite question d'arithmétique qui me semble pas simple du tout (j'ai déjà pas mal réfléchi sans trouver). Ce n'est pas moi qui ai inventé cette question et peut-être que certains d'entre vous la connaissent. Je nai pas la réponse.

On considère deux entiers strictement positifs $\text{[math]}$ et $\text{[math]}$ tels que $\text{[math]}$ divise $\text{[math]}$ . Il faut montrer que dans ce cas:
$\text{[math]}$
est forcément un carré parfait.

La première chose que j'ai faite c'est de vérifier par ordinateur, pour des valeurs de $\text{[math]}$ et $\text{[math]}$ de $\text{[math]}$ à $\text{[math]}$ que c'était vrai et on peut alors constater qu'on obtient tous les premiers carrés. J'ai également observé qu'on avait souvent $\text{[math]}$ ou $\text{[math]}$ mais ce n'était pas les seules possibilités. Effectivement, en supposant que $\text{[math]}$ et $\text{[math]}$ pour un certain entier $\text{[math]}$ et pour certains entiers naturels $\text{[math]}$ et $\text{[math]}$ j'arrive à montrer qu'on a forcément, si $\text{[math]}$ est différent de $\text{[math]}$ ou $\text{[math]}$ , $\text{[math]}$ ou $\text{[math]}$ . Ce qui est déjà un résultat. J'avais pensé aussi travailler dans $\text{[math]}$ pour factoriser $\text{[math]}$ mais je suis pas allé plus loin pour l'instant.

Si pour quelqu'un la réponse est évidente je suis preneur

invite2220c077 · 21/04/2009, 15h56

C'est effectivement un exercice difficile, voire très difficile si on ne connaît pas la méthode dite "Viète Jumping" qui permet de résoudre de manière "simple" ce type d'exercices.
Pour instance, cet exercice a été donné aux Olympiades Internationales de Mathématiques de 1988, et seulement 2-3 personnes l'avaient réussi (sur 500), à l'époque où cette méthode n'était pas connue des "olympiadeurs". Je te propose une solution (ce n'est évidemment pas la mienne ...) basée sur cette fameuse méthode :

Soit $\text{[math]}$ . On fixe $\text{[math]}$ et on considère toutes les paires $\text{[math]}$ qui satisfont l'équation, c'est-à-dire, on considère

$\text{[math]}$

J'affirme que parmi toutes ces paires il en existe une telle que $\text{[math]}$ et $\text{[math]}$ . Pour cela, on suppose que $\text{[math]}$ n'est pas un carré parfait et qu'il existe une paire $\text{[math]}$ qui minimise $\text{[math]}$ .

Sans perte de généralité, on peut toujours supposer $\text{[math]}$ . On considère l'équation :

$\text{[math]}$

qui équivaut à

$\text{[math]}$

On sait que $\text{[math]}$ est une racine de cette équation. D'après les relations de Viète :

$\text{[math]}$

La première relation implique que $\text{[math]}$ est un entier, la seconde que $\text{[math]}$ est différent de 0 sinon $\text{[math]}$ cela contredirait notre hypothèse de départ. De plus, $\text{[math]}$ ne peut être négatif sinon :

$\text{[math]}$

une contradiction. Ainsi $\text{[math]}$ et donc $\text{[math]}$ . Comme $\text{[math]}$ on a :

$\text{[math]}$

ainsi $\text{[math]}$ , ce qui contredit la minimalité de $\text{[math]}$ .

invite2220c077 · 21/04/2009, 16h02

Généralisation :

Si $\text{[math]}$ , $\text{[math]}$ et $\text{[math]}$ sont trois entiers naturels tels que $\text{[math]}$ , alors $\text{[math]}$ est un carré parfait.

invite2220c077 · 21/04/2009, 16h11

Après vérifications, en fait "seulement" 10 personnes ont eu 7/7 à cette question, sur 268. La solution que j'ai donnée à été écrite par l'un d'eux, Emanouil Atanassov un bulgare, ce qui lui a valu un prix spécial.

Petite parenthèse, Terence Tao avait participé cette année là, même lui n'a eu "que" 1/7

. Mais il s'est rattrapé quelques temps plus tard avec la médaille Fields ...

A voir en vidéo sur Futura · Aujourd'hui

invite2220c077 · 21/04/2009, 16h19

On peut résoudre de la même manière l'exercice des OIM de 2007 :

Soient $\text{[math]}$ et $\text{[math]}$ des entiers naturels. Montrer que si $\text{[math]}$ divise $\text{[math]}$ , alors $\text{[math]}$ .

**leon1789** · 21/04/2009, 17h37

Merci Zweig pour tout ceci.

invite2220c077 · 21/04/2009, 17h55

Au plaisir.

**leon1789** · 21/04/2009, 19h31

Je propose juste une variation dans la dernière ligne droite de ta preuve.

Envoyé par -Zweig-

On fixe $\text{[math]}$ et on considère toutes les paires $\text{[math]}$ qui satisfont l'équation $\text{[math]}$ , c'est-à-dire, on considère

$\text{[math]}$

J'affirme que parmi toutes ces paires il en existe une telle que $\text{[math]}$ et $\text{[math]}$ .

Ok. Prouvons-le.

Envoyé par -Zweig-

Pour cela, on suppose que $\text{[math]}$ n'est pas un carré parfait

Personnellement, je vais éviter de prendre cette hypothèse, because allergie aux raisonnements par l'absurde

Envoyé par -Zweig-

Il existe une paire $\text{[math]}$ qui minimise $\text{[math]}$ .

Sans perte de généralité, on peut toujours supposer $\text{[math]}$ . On considère l'équation :

$\text{[math]}$
donc
$\text{[math]}$

On sait que $\text{[math]}$ est une racine de cette équation. D'après les relations de Viète :
$\text{[math]}$

Juste une remarque : on peut diviser par A sous condition A > 0.
c'est-à-dire k>0 (c'était sous-entendu depuis le début).

Du coup $\text{[math]}$ et B ne peuvent pas être nuls simultanément.

Envoyé par -Zweig-

La première relation implique que $\text{[math]}$ est un entier

oui, pas de problème.

De plus $\text{[math]}$ , ce qui entraine $\text{[math]}$ , puis $\text{[math]}$ . En particulier $\text{[math]}$

Comme $\text{[math]}$ et k>0, on a $\text{[math]}$ ainsi $\text{[math]}$ ,
puis, par minimalité de $\text{[math]}$ où A,B sont des entiers naturels, il vient a $\text{[math]}$ .

Or $\text{[math]}$ donc B=0 et $\text{[math]}$
(et $\text{[math]}$ ) .

invite986312212 · 22/04/2009, 09h21

jolie démonstration Zweig.
comment connais-tu si bien les olympiades de maths?

Envoyé par -Zweig-

Généralisation :

Si $\text{[math]}$ , $\text{[math]}$ et $\text{[math]}$ sont trois entiers naturels tels que $\text{[math]}$ , alors $\text{[math]}$ est un carré parfait.

autres généralisations possibles:

si abc+1 divise a^2+b^2+c^2 le quotient est-il toujours un carré?

ou

si ab+1 divise a^3+b^3 le quotient est-il un cube?

etc

**KerLannais** · 22/04/2009, 10h14

Re,

Ok, merci c'est une très jolie démonstration

invite2220c077 · 22/04/2009, 12h46

Ambrosio > Car je me suis pas mal entraîné pour les OIM mais bon, je n'ai pas été assez bon pour me sélectionner dans l'équipe de France

... Et cette petite anecdote se trouve dans un de mes bouquins de préparation. Pour finir la petite histoire, ce problème avait d'abord été posé aux six membres du comité des problèmes australiens (comme cette OIM se passait en Australie en 88) : personne ne put le résoudre. Parmi ces six membres, deux étaient Georges Szekeres et sa femme, tous deux des résolveurs chevronnés et créateurs de problèmes ... Après ça, il fut envoyé à 4 théoriciens des nombres australiens de très grande réputation : aucun ne put le résoudre dans le temps imparti (6h). Finalement, le jury décida après maintes discussions de le présenter aux OIM

.

Autre problème réputé "monstrueusement difficile" posé aux Olympiades (moldaves je crois). Ce sont des mathématiciens qui ont trouvé ce problème encore inconnu dans les papiers ... d'Euler ! Aucun participant n'a pu trouver une solution. Après l'olympiade, un théoricien écrivit dans un journal russe que ce problème était bien au-dessus de niveau des lycéens. En fait il existe une solution extrêmement élémentaire et atrocement astucieuse. Elle est due à un olympiadeur allemand. Je vous laisse d'abord chercher avant de la poster.

Montrer que si $\text{[math]}$ , alors il existe des entiers naturels impairs $\text{[math]}$ et $\text{[math]}$ tels que $\text{[math]}$

invite986312212 · 22/04/2009, 15h20

message suprimé

**leon1789** · 23/04/2009, 18h25

Envoyé par KerLannais

On considère deux entiers strictement positifs $\text{[math]}$ et $\text{[math]}$ tels que $\text{[math]}$ divise $\text{[math]}$ . Il faut montrer que dans ce cas:
$\text{[math]}$
est forcément un carré parfait.

La première chose que j'ai faite c'est de vérifier par ordinateur, pour des valeurs de $\text{[math]}$ et $\text{[math]}$ de $\text{[math]}$ à $\text{[math]}$ que c'était vrai et on peut alors constater qu'on obtient tous les premiers carrés. J'ai également observé qu'on avait souvent $\text{[math]}$ ou $\text{[math]}$ mais ce n'était pas les seules possibilités.

Oui, et cela n'est pas étonnant.
Les exemples triviaux de $\text{[math]}$ sont (a,b)=(0,z) et son symétrique.
Les premiers exemples simples sont $\text{[math]}$ comme tu dis.

Mais on en trouve d'autres : par exemple, $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , ...

Comment trouver des exemples ?

**leon1789** · 24/04/2009, 08h32

Envoyé par KerLannais

On considère deux entiers strictement positifs $\text{[math]}$ et $\text{[math]}$ tels que $\text{[math]}$ divise $\text{[math]}$ . Il faut montrer que dans ce cas:
$\text{[math]}$ est forcément un carré parfait.

Autre variante de la preuve de Zweig, mais via cette preuve par récurrence, il apparaît clairement que $\text{[math]}$ !!

On fixe un entier k tel que $\text{[math]}$ n'est pas vide.
Soit $\text{[math]}$ : aucune hypothèse ni sur k, ni sur (A,B).

Quitte à échanger A et B, on peut supposer $\text{[math]}$ .
- Si B=0 alors A²=k=pgcd(A,B)² et c'est terminé.
- Si B>0 alors on regarde l'équation en x suivante : $\text{[math]}$
c'est-à-dire x² -kB.x + B²-k = 0
On sait que A est une solution, donc il en existe une seconde qui s'écrit $\text{[math]}$ .
On démontre alors que $\text{[math]}$ est un entier naturel tel que $\text{[math]}$ . On applique l'hypothèse de récurrence à (x,B), remplaçant le couple (A,B).

**leon1789** · 26/04/2009, 11h10

Envoyé par leon1789

Autre variante de la preuve de Zweig, mais via cette preuve par récurrence, il apparaît clairement que $\text{[math]}$ !!

J'aurais bien voulu savoir si on peut trouver une preuve "directe" de cette égalité, i.e. sans récurrence et sans raisonnement par l'absurde.

Le fait que $\text{[math]}$ divise $\text{[math]}$ est facile. Mais ensuite ?

**leon1789** · 27/04/2009, 13h15

Envoyé par leon1789

Autre variante de la preuve de Zweig, mais via cette preuve par récurrence, il apparaît clairement que $\text{[math]}$ !!

En fait, en lisant ce document http://www.mathpages.com/home/kmath334.htm ,
je vois que ce résultat se généralise à $\text{[math]}$
lorsque $\text{[math]}$ (et $\text{[math]}$ divise $\text{[math]}$ bien sûr)

Dans le document, il y a un truc qui m'étonne un peu : en posant $\text{[math]}$ , l'auteur prouve que N est un carré, mais il ne parle jamais du fait que N =pgcd(a,b)²... (qui est indépendant de K)

Et en ce concerne la preuve de cette généralisation, il suffit de reprendre la preuve par récurrence ci-dessus sans rien changer.

invitebe08d051 · 27/04/2009, 13h48

Salut,

Envoyé par -Zweig-

Montrer que si $\text{[math]}$ , alors il existe des entiers naturels impairs $\text{[math]}$ et $\text{[math]}$ tels que $\text{[math]}$

Je viens de trouver une solution mais qui me parait un peu trop facile.
On doit bien montrer que:
$\text{[math]}$
Ce qui revient à montrer que les équations:
$\text{[math]}$
$\text{[math]}$
$\text{[math]}$
n'admettent pas de solutions dans $\text{[math]}$ .

Quelqu'un peut confirmer??
Merci

invité576543 · 27/04/2009, 14h06

Envoyé par mimo13

Quelqu'un peut confirmer??

Je ne peux pas

C'est plutôt montrer que 7x²+y²=8, =16, ...,2ⁿ admettent toutes des solutions impaires, comme par exemple 32 = 7.1²+5² ou 64=7.3²+1². (C'est facile de montrer qu'il y a toujours des solutions si on accepte x et y pairs...)

Cordialement,

**leon1789** · 28/04/2009, 13h33

Dans la preuve donnée par Zweig,

Envoyé par -Zweig-

Soit $\text{[math]}$ . On fixe $\text{[math]}$ et on considère toutes les paires $\text{[math]}$ qui satisfont l'équation, c'est-à-dire, on considère

$\text{[math]}$

J'affirme que parmi toutes ces paires il en existe une telle que $\text{[math]}$ et $\text{[math]}$ . Pour cela, on suppose que $\text{[math]}$ n'est pas un carré parfait et qu'il existe une paire $\text{[math]}$ qui minimise $\text{[math]}$ .

Sans perte de généralité, on peut toujours supposer $\text{[math]}$ . On considère l'équation :

$\text{[math]}$

qui équivaut à

$\text{[math]}$

On sait que $\text{[math]}$ est une racine de cette équation. D'après les relations de Viète :

$\text{[math]}$

La première relation implique que $\text{[math]}$ est un entier, la seconde que $\text{[math]}$ est différent de 0 sinon $\text{[math]}$ cela contredirait notre hypothèse de départ. De plus, $\text{[math]}$ ne peut être négatif sinon :

$\text{[math]}$

une contradiction. Ainsi $\text{[math]}$ et donc $\text{[math]}$ . Comme $\text{[math]}$ on a :

$\text{[math]}$

ainsi $\text{[math]}$ , ce qui contredit la minimalité de $\text{[math]}$ .

il y a un truc qui m'amuse un peu

:
la seule fois où est utilisée explicitement l'hypothèse "k non carré", c'est pour démontrer $\text{[math]}$ . Or cela ne sert pas dans la suite puisque $\text{[math]}$ suffit à conclure, comme le fait Zweig...

L'hypothèse "k non carré" n'est donc pas nécessaire pour obtenir une contradiction ?
Qu'en pensez-vous ?
(La réponse n'est pas compliquée

)

**acx01b** · 28/04/2009, 14h28

si on a l'hypothèse "k n'est pas un carré" et A >= B, on rajoute B > 0 (ce qui a été oublié ici) pour avoir la propriété que x_2 n'est pas négatif, et enfin la contradiction finale

si on n'a pas l'hypothèse "k n'est pas un carré" et qu'on a juste A >= B >= 0

le cas B = 0 fait qu'on ne peut pas conclure sur le signe de x_2, et donc on n'a pas la contradiction finale

**acx01b** · 28/04/2009, 14h36

le cas x_2 = 0 de la même manière ne permet pas de déduire que x_2 ne peut être négatif

**leon1789** · 28/04/2009, 14h44

Envoyé par acx01b

si on a l'hypothèse "k n'est pas un carré" et A >= B, on rajoute B > 0 (ce qui a été oublié ici) pour avoir la propriété que x_2 n'est pas négatif, et enfin la contradiction finale

. Oui .

**KerLannais** · 28/04/2009, 15h04

Sur le problème $\text{[math]}$ , le seul truc que j'ai réussi à montrer pour l'instant mais je pense que ça aide pas (et en plus c'est vraiment évident à montrer) c'est que le problème est équivalent au suivant: soit pour $\text{[math]}$
$\text{[math]}$
la suite des sommes des premiers entiers successifs. Alors pour tout $\text{[math]}$ il existe des entiers naturels $\text{[math]}$ et $\text{[math]}$ tels que:
$\text{[math]}$
Je sais c'est pas formidable

peut-être ça peut inspirer quelqu'un ou peut-être que ça apporte rien du tout mais bon au moins j'aurai dit quelque chose sur le sujet.

Sinon, mes cours d'arithmétique sont loin, quelqu'un pourrait-il me rappeler les propriétés de l'anneau $\text{[math]}$
est-il euclidien ? factoriel ? principal ? de Dedekind ...

invite986312212 · 28/04/2009, 15h19

il est euclidien. Mais j'ai l'impression que regarder ce qui se passe dans $\text{[math]}$ permettrait plutôt de montrer qu'il n'y a pas de solution si c'était le cas.

**leon1789** · 28/04/2009, 15h25

Envoyé par KerLannais

Sinon, mes cours d'arithmétique sont loin, quelqu'un pourrait-il me rappeler les propriétés de l'anneau $\text{[math]}$
est-il euclidien ? factoriel ? principal ? de Dedekind ...

Rien de tout ça car $\text{[math]}$ n'est pas intégralement clos.

invite5f67e63a · 28/04/2009, 15h40

Ce qu'il faut regarder c'est $\text{[math]}$ pour qu'il soit Dedekind.

invite986312212 · 28/04/2009, 16h18

oui c'est bien celui-ci qui est euclidien, c'est l'anneau des entiers de Q(sqrt(-7)).

**acx01b** · 28/04/2009, 22h32

bonsoir

si on a $\text{[math]}$ avec a et b impairs
alors $\text{[math]}$
ensuite on a 2 factorisations possibles :
$\text{[math]}$
$\text{[math]}$

comme a et b sont impairs, a+b, a-b, 7a-b, 7a+b sont pairs donc on peut tout diviser par 4 ce qui donne:

$\text{[math]}$

on doit enfin choisir entre la première et la deuxième écriture:
si $\text{[math]}$ est pair alors $\text{[math]}$ est impair et on choisi la seconde, sinon on choisi la première

et donc on a : $\text{[math]}$ avec A et B impairs

invite2220c077 · 28/04/2009, 22h53

Bravo !

**leon1789** · 29/04/2009, 17h38

Effectivement, chapeau !

Une question d'arithmétique difficile

Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Re : Une question d'arithmétique difficile

Discussions similaires

[Divers] Question difficile : Obtenir une très faible luminosité avec un variateur de lumière

Question d'arithmétique

Question d'arithmétique

Question d'arithmétique

Une question d'arithmétique...