Aller au contenu

Shortlist 2010, N4

Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : Turkey

Concepts : Congruences, théorèmes de Fermat et d'Euler · Principe des tiroirs · Théorème des restes chinois

Solution officielle : Shortlist officielle 2010 (avec solutions), p. 70 (page 71 du PDF)

Énoncé

Let \(a, b\) be integers, and let \(P(x) = ax^3 + bx\). For any positive integer \(n\) we say that the pair \((a, b)\) is \(n\)-good if \(n \mid P(m) - P(k)\) implies \(n \mid m - k\) for all integers \(m, k\). We say that \((a, b)\) is very good if \((a, b)\) is \(n\)-good for infinitely many positive integers \(n\).

(a) Find a pair \((a, b)\) which is \(51\)-good, but not very good.

(b) Show that all \(2010\)-good pairs are very good.

Indices : les idées clés
  • (a) : \(P(x) = x^3 - 51^2x\) vérifie \(P(51) = P(0)\), donc n'est \(n\)-bon que pour \(n \mid 51\) ; et \(m^3 \equiv k^3\) donne \(m \equiv k\) modulo \(3\) et \(17\) par Fermat.
  • Restes chinois : un couple \(2010\)-bon est \(67\)-bon ; puis \(67 \mid a\), car sinon deux ensembles de \(34\) résidus se rencontrent et fournissent \(m \not\equiv k\) avec \(P(m) \equiv P(k)\).
  • Congruences : avec \(67 \mid a\) et \(67 \nmid b\), le facteur \(a(m^2 + mk + k^2) + b\) est premier avec \(67\), donc \((a, b)\) est \(67^i\)-bon pour tout \(i\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2010 (une solution et deux remarques).

Solution

(a) Montrons que le couple \((1, -51^2)\) est \(51\)-bon mais pas très bon. Soit \(P(x) = x^3 - 51^2x\). Comme \(P(51) = P(0)\), le couple \((1, -51^2)\) n'est \(n\)-bon pour aucun entier \(n > 0\) qui ne divise pas \(51\). Donc \((1, -51^2)\) n'est pas très bon.

D'autre part, si \(P(m) \equiv P(k) \pmod{51}\), alors \(m^3 \equiv k^3 \pmod{51}\). D'après le petit théorème de Fermat, on en déduit

\[m \equiv m^3 \equiv k^3 \equiv k \pmod 3 \qquad \text{et} \qquad m \equiv m^{33} \equiv k^{33} \equiv k \pmod{17}.\]

On a donc \(m \equiv k \pmod{51}\), et \((1, -51^2)\) est \(51\)-bon.

(b) Nous allons montrer que si un couple \((a, b)\) est \(2010\)-bon, alors \((a, b)\) est \(67^i\)-bon pour tout entier \(i > 0\).

Affirmation 1. Si \((a, b)\) est \(2010\)-bon, alors \((a, b)\) est \(67\)-bon.

Preuve. Supposons \(P(m) \equiv P(k) \pmod{67}\). Comme \(67\) et \(30\) sont premiers entre eux, il existe des entiers \(m'\) et \(k'\) tels que \(k' \equiv k \pmod{67}\), \(k' \equiv 0 \pmod{30}\), et \(m' \equiv m \pmod{67}\), \(m' \equiv 0 \pmod{30}\). On a alors \(P(m') \equiv P(0) \equiv P(k') \pmod{30}\) et \(P(m') \equiv P(m) \equiv P(k) \equiv P(k') \pmod{67}\), donc \(P(m') \equiv P(k') \pmod{2010}\). Cela implique \(m' \equiv k' \pmod{2010}\) puisque \((a, b)\) est \(2010\)-bon. Il s'ensuit que \(m \equiv m' \equiv k' \equiv k \pmod{67}\). Donc \((a, b)\) est \(67\)-bon. \(\square\)

Affirmation 2. Si \((a, b)\) est \(67\)-bon, alors \(67 \mid a\).

Preuve. Supposons \(67 \nmid a\). Considérons les ensembles \(\{at^2 \bmod 67 : 0 \leq t \leq 33\}\) et \(\{-3as^2 - b \bmod 67 : 0 \leq s \leq 33\}\). Comme \(a \not\equiv 0 \pmod{67}\), chacun de ces ensembles a \(34\) éléments. Ils ont donc au moins un élément commun. Si \(at^2 \equiv -3as^2 - b \pmod{67}\), alors, pour \(m = t \pm s\), \(k = \mp 2s\), on a

\[P(m) - P(k) = a(m^3 - k^3) + b(m - k) = (m - k)\big(a(m^2 + mk + k^2) + b\big) = (t \pm 3s)(at^2 + 3as^2 + b) \equiv 0 \pmod{67}.\]

Comme \((a, b)\) est \(67\)-bon, on doit avoir \(m \equiv k \pmod{67}\) dans les deux cas, c'est-à-dire \(t \equiv 3s \pmod{67}\) et \(t \equiv -3s \pmod{67}\). Cela signifie que \(t \equiv s \equiv 0 \pmod{67}\) et \(b \equiv -3as^2 - at^2 \equiv 0 \pmod{67}\). Mais alors \(67 \mid P(7) - P(2) = 67 \cdot 5a + 5b\) et \(67 \nmid 7 - 2\), ce qui contredit le fait que \((a, b)\) est \(67\)-bon. \(\square\)

Affirmation 3. Si \((a, b)\) est \(2010\)-bon, alors \((a, b)\) est \(67^i\)-bon pour tout \(i \geq 1\).

Preuve. D'après l'affirmation 2, on a \(67 \mid a\). Si \(67 \mid b\), alors \(P(x) \equiv P(0) \pmod{67}\) pour tout \(x\), ce qui contredit le fait que \((a, b)\) est \(67\)-bon. Donc \(67 \nmid b\).

Supposons \(67^i \mid P(m) - P(k) = (m - k)\big(a(m^2 + mk + k^2) + b\big)\). Comme \(67 \mid a\) et \(67 \nmid b\), le second facteur \(a(m^2 + mk + k^2) + b\) est premier avec \(67\), donc \(67^i \mid m - k\). Le couple \((a, b)\) est donc \(67^i\)-bon. \(\square\) \(\blacksquare\)

Remarques

Remarque 1. Dans la preuve de l'affirmation 2, on peut aussi raisonner ainsi. Comme \(3\) n'est pas un résidu quadratique modulo \(67\), l'une des congruences \(au^2 \equiv -b \pmod{67}\) ou \(3av^2 \equiv -b \pmod{67}\) a une solution. Les choix \((m, k) = (u, 0)\) dans le premier cas et \((m, k) = (v, -2v)\) dans le second donnent \(b \equiv 0 \pmod{67}\).

Remarque 2. Le couple \((67, 30)\) est \(n\)-bon si et seulement si \(n = d \cdot 67^i\), où \(d \mid 30\) et \(i \geq 0\). Cela montre que, dans la partie (b), il faut travailler avec les grandes puissances de \(67\) pour aboutir. La propriété clé du nombre \(67\) est qu'il est de la forme \(3k + 1\), de sorte qu'il existe une racine cubique de l'unité non triviale modulo \(67\).