Exercice national 2 — Entiers \(N\)-décomposables (spécialité maths)

A2/B1. Le système \(\{k=q+r,\ k^2=qN+r\}\) donne, en éliminant \(r\) : \(k^2-k=q(N-1)\), soit \(q=\dfrac{k(k-1)}{N-1}\) (pour \(N\ge2\)) qui doit être un entier naturel entre 0 et \(k\).

B3. L'équation \(x^2-x-q(N-1)=0\) a pour racine positive \(x=\dfrac{1+\sqrt{1+4q(N-1)}}2\) : chercher pour quels \(q\) le discriminant est un carré parfait impair.

B4. Si \((q,r)\) convient pour \(k\), chercher un couple \((q',r')\) adapté à \(N-k\) en utilisant la symétrie de l'équation \(k^2-k=q(N-1)\) par rapport à \(k\mapsto N-k\) (développer \((N-k)^2-(N-k)\) et comparer à \(k^2-k\)).

B6. Utiliser le résultat de la question B4 : les entiers \(N\)-décomposables se regroupent par paires \(\{k,N-k\}\), sauf éventuellement le cas \(k=N-k=N/2\) — déjà exclu par la question B5 quand \(N\) est pair et \(\ge4\).

Clé de tout l'exercice. En éliminant \(r=k-q\) dans \(k^2=Nq+r\), on obtient pour tout \(N\ge2\) : \(k^2-k=q(N-1)\), soit \(q=\dfrac{k(k-1)}{N-1}\). Ainsi \(k\) est \(N\)-décomposable ssi \(N-1\) divise \(k(k-1)\) et \(0\le k\le N\) (cette dernière condition venant de \(q\le k\)). Cette reformulation simplifie presque toutes les questions suivantes.

A.1.

Soit \(k\) un entier naturel. Il est \(N\)-décomposable s'il existe \(q,r\in\mathbb{N}\) tels que \(k = q+r\) et \(k^2 = qN + r\).

* 7 est-il 22-décomposable ?

On cherche \(q,r\in\mathbb{N}\) avec \(q+r=7\) et \(7^2 = 49 = 22q + r\).

De \(r = 7-q\), on substitue : \(49 = 22q + 7 - q \Rightarrow 49 = 21q + 7 \Rightarrow 21q = 42 \Rightarrow q = 2\).

Alors \(r = 7-2 = 5\). Les deux sont entiers naturels. Donc 7 est 22-décomposable.

* 7 est-il 10-décomposable ?

On cherche \(q,r\in\mathbb{N}\) avec \(q+r=7\) et \(49 = 10q + r\).

\(r = 7-q\) donne \(49 = 10q + 7 - q = 9q + 7 \Rightarrow 9q = 42 \Rightarrow q = \frac{42}{9} = \frac{14}{3}\), non entier. Donc 7 n'est pas 10-décomposable.

* 45 est-il 100-décomposable ?

On cherche \(q,r\in\mathbb{N}\) avec \(q+r=45\) et \(45^2 = 2025 = 100q + r\).

\(r = 45-q\) donne \(2025 = 100q + 45 - q = 99q + 45 \Rightarrow 99q = 1980 \Rightarrow q = 20\).

Alors \(r = 45-20 = 25\). Les deux sont entiers naturels. Donc 45 est 100-décomposable.

A.2.

Pour \(N=1\), la condition est : \(k = q+r\) et \(k^2 = q\cdot 1 + r = q+r = k\).

Donc \(k^2 = k \Rightarrow k(k-1)=0 \Rightarrow k=0\) ou \(k=1\).

Ce sont deux entiers, donc exactement deux entiers 1-décomposables (0 et 1).

Pour \(N=2\), condition : \(k = q+r\) et \(k^2 = 2q + r\).

En substituant \(r = k-q\), on a \(k^2 = 2q + k - q = q + k \Rightarrow q = k^2 - k\).

Comme \(q\) doit être entier naturel et \(0 \le q \le k\) (car \(r\ge 0\)), on a \(0 \le k^2 - k \le k\).

\(k^2 - k \ge 0 \Rightarrow k(k-1)\ge 0 \Rightarrow k\ge 1\) ou \(k=0\).

\(k^2 - k \le k \Rightarrow k^2 - 2k \le 0 \Rightarrow k(k-2)\le 0 \Rightarrow 0\le k\le 2\).

Donc \(k\in\{0,1,2\}\). Vérifions :

• \(k=0\) : \(q=0\), \(r=0\) convient.

• \(k=1\) : \(q=0\), \(r=1\) convient.

• \(k=2\) : \(q=2\), \(r=0\) convient.

Soit trois entiers 2-décomposables.

A.3.

* \(N\) est-il \(N\)-décomposable ?

On cherche \(q,r\) tels que \(N = q+r\) et \(N^2 = Nq + r\).

\(r = N-q\) donne \(N^2 = Nq + N - q = q(N-1) + N\).

Donc \(q(N-1) = N^2 - N = N(N-1)\). Si \(N\ge 2\), on simplifie par \(N-1\) (non nul) : \(q = N\). Alors \(r = N-N = 0\).

Si \(N=1\), la condition devient \(1 = q+r\) et \(1 = q+r\) (car \(N^2=1\)), donc tout couple convient, en particulier \(q=1, r=0\).

Donc pour tout \(N\ge 1\), \(N\) est \(N\)-décomposable (avec \(q=N, r=0\)).

* Montrer que \(N-1\) l'est toujours.

On cherche \(q,r\) tels que \(N-1 = q+r\) et \((N-1)^2 = Nq + r\).

\(r = N-1-q\) donne \((N-1)^2 = Nq + N-1 - q = q(N-1) + N-1\).

Donc \(q(N-1) = (N-1)^2 - (N-1) = (N-1)(N-2)\). Si \(N\ge 2\), on simplifie par \(N-1\) : \(q = N-2\). Alors \(r = N-1 - (N-2) = 1\).

Si \(N=1\), \(N-1=0\) est 1-décomposable (vu en A.2). Donc \(N-1\) est toujours \(N\)-décomposable.

* Montrer que si \(N\ge 4\), 2 n'est pas \(N\)-décomposable.

Pour \(k=2\), on a \(2 = q+r\) et \(4 = Nq + r\).

\(r = 2-q\) donne \(4 = Nq + 2 - q = q(N-1) + 2 \Rightarrow q(N-1) = 2\).

Donc \(q = \frac{2}{N-1}\). Pour que \(q\) soit entier naturel, \(N-1\) doit diviser 2, donc \(N-1 \in \{1,2\}\), soit \(N\in\{2,3\}\).

Si \(N\ge 4\), \(N-1\ge 3\) ne divise pas 2, donc pas de solution. Ainsi 2 n'est pas \(N\)-décomposable pour \(N\ge 4\).

B.1.

* Si \(k\) est \(N\)-décomposable, montrer \(0\le k\le N\).

On a \(k = q+r\) et \(k^2 = Nq + r\). Comme \(q,r\ge 0\), on a \(k^2 \ge Nq\) et \(k^2 \ge r\).

De \(k = q+r\), on tire \(r = k-q \ge 0 \Rightarrow q\le k\).

Alors \(k^2 = Nq + r \le Nk + r\) (car \(q\le k\)). Mais \(r\le k\) (car \(q\ge 0\)), donc \(k^2 \le Nk + k = k(N+1)\).

Si \(k>0\), on divise par \(k\) : \(k \le N+1\). Mais on peut mieux :

De \(k^2 = Nq + r\) et \(r = k-q\), on a \(k^2 = Nq + k - q = q(N-1) + k\).

Donc \(q(N-1) = k^2 - k = k(k-1)\). Comme \(q\ge 0\), on a \(k(k-1)\ge 0\), donc \(k\ge 1\) ou \(k=0\).

De plus, \(q\le k\) donne \(k(k-1) \le k(N-1) \Rightarrow\) si \(k>0\), \(k-1 \le N-1 \Rightarrow k\le N\).

Donc \(0\le k\le N\).

* Lister les entiers 3- et 4-décomposables.

Pour \(N=3\) : on teste \(k=0,1,2,3\).

• \(k=0\) : \(0=q+r\), \(0=3q+r\) donne \(q=r=0\) convient.

• \(k=1\) : \(1=q+r\), \(1=3q+r\) donne \(r=1-q\), \(1=3q+1-q=2q+1 \Rightarrow 2q=0 \Rightarrow q=0, r=1\) convient.

• \(k=2\) : \(2=q+r\), \(4=3q+r\) donne \(r=2-q\), \(4=3q+2-q=2q+2 \Rightarrow 2q=2 \Rightarrow q=1, r=1\) convient.

• \(k=3\) : \(3=q+r\), \(9=3q+r\) donne \(r=3-q\), \(9=3q+3-q=2q+3 \Rightarrow 2q=6 \Rightarrow q=3, r=0\) convient.

Donc tous les entiers de 0 à 3 sont 3-décomposables : \(\{0,1,2,3\}\).

Pour \(N=4\) : on teste \(k=0,1,2,3,4\).

• \(k=0\) : \(q=r=0\) convient.

• \(k=1\) : \(1=q+r\), \(1=4q+r\) donne \(r=1-q\), \(1=4q+1-q=3q+1 \Rightarrow 3q=0 \Rightarrow q=0, r=1\) convient.

• \(k=2\) : \(2=q+r\), \(4=4q+r\) donne \(r=2-q\), \(4=4q+2-q=3q+2 \Rightarrow 3q=2 \Rightarrow q\) non entier. Donc 2 n'est pas 4-décomposable.

• \(k=3\) : \(3=q+r\), \(9=4q+r\) donne \(r=3-q\), \(9=4q+3-q=3q+3 \Rightarrow 3q=6 \Rightarrow q=2, r=1\) convient.

• \(k=4\) : \(4=q+r\), \(16=4q+r\) donne \(r=4-q\), \(16=4q+4-q=3q+4 \Rightarrow 3q=12 \Rightarrow q=4, r=0\) convient.

Donc les entiers 4-décomposables sont \(\{0,1,3,4\}\).

B.2.

Si \(N\ge 2\), montrons l'unicité du couple \((q,r)\).

Supposons deux couples \((q,r)\) et \((q',r')\) tels que \(k = q+r = q'+r'\) et \(k^2 = Nq+r = Nq'+r'\).

En soustrayant : \(N(q-q') + (r-r') = 0\). Mais \(r-r' = (k-q)-(k-q') = -(q-q')\).

Donc \(N(q-q') - (q-q') = (N-1)(q-q') = 0\). Comme \(N\ge 2\), \(N-1\neq 0\), donc \(q=q'\), puis \(r=r'\). D'où l'unicité.

B.3.

* Montrer que \(k\) est \(N\)-décomposable ssi il existe \(q\) (\(1\le q\le k\)) tel que \(k^2 - k - q(N-1)=0\).

De la relation \(k^2 = Nq + r\) et \(r = k-q\), on a \(k^2 = Nq + k - q = q(N-1) + k\).

Donc \(k^2 - k = q(N-1)\). Ainsi \(q = \frac{k(k-1)}{N-1}\).

Pour que \(q\) soit entier naturel, il faut que \(N-1\) divise \(k(k-1)\). De plus, \(q\) doit vérifier \(0\le q\le k\) (car \(r\ge 0\)).

Comme \(k(k-1)\ge 0\), \(q\ge 0\) automatique. La condition \(q\le k\) équivaut à \(\frac{k(k-1)}{N-1} \le k \Rightarrow\) si \(k>0\), \(k-1 \le N-1 \Rightarrow k\le N\).

Donc \(k\) est \(N\)-décomposable ssi \(N-1\) divise \(k(k-1)\) et \(k\le N\).

L'équation \(k^2 - k - q(N-1)=0\) est équivalente à \(q = \frac{k(k-1)}{N-1}\), donc c'est la même condition.

* Montrer que \(2^{p-1}(2^p-1)\) est \(2^{2p}\)-décomposable.

Soit \(k = 2^{p-1}(2^p-1)\) et \(N = 2^{2p}\), donc \(N-1=(2^p-1)(2^p+1)\). D'après la clé ci-dessus, il suffit de calculer \(q=\dfrac{k(k-1)}{N-1}\) et de vérifier qu'il est entier avec \(q\le k\). En développant, \(q=2^{p-1}(2^{p-1}-1)\) : c'est bien un entier naturel, et \(q\le k\) puisque \(2^{p-1}-1<2^p-1\). Donc \(k\) est \(N\)-décomposable, avec \(r=k-q=2^{2p-2}\).

B.4.

Si \(k\) est \(N\)-décomposable, \(N-1\) divise \(k(k-1)\). Or modulo \(N-1\), on a \(N\equiv1\), donc \(N-k\equiv1-k\), d'où \((N-k)(N-k-1)\equiv(1-k)(-k)=k(k-1)\pmod{N-1}\) : \(N-1\) divise donc aussi \((N-k)(N-k-1)\). Comme de plus \(0\le N-k\le N\) (car \(0\le k\le N\)), \(N-k\) est \(N\)-décomposable, avec \(q'=\frac{(N-k)(N-k-1)}{N-1}\) et \(r'=(N-k)-q'\).

B.5.

Si \(N\) pair \(\ge 4\), montrons que \(N/2\) n'est pas \(N\)-décomposable.

Supposons \(k = N/2\). Alors \(k(k-1) = \frac{N}{2}(\frac{N}{2}-1) = \frac{N(N-2)}{4}\).

Pour que \(k\) soit \(N\)-décomposable, il faut que \(N-1\) divise \(k(k-1)\).

Donc \(N-1\) doit diviser \(\frac{N(N-2)}{4}\).

Comme \(N\) est pair, écrivons \(N=2m\) avec \(m\ge 2\). Alors \(k=m\), \(k(k-1)=m(m-1)\), et \(N-1=2m-1\).

Il faut \(2m-1\) divise \(m(m-1)\).

Or \(2m-1\) et \(m\) sont premiers entre eux ? \(pgcd(2m-1, m) = pgcd(m-1, m)=1\).

De même, \(pgcd(2m-1, m-1) = pgcd(2m-1 - 2(m-1), m-1) = pgcd(1, m-1)=1\).

Donc \(2m-1\) est premier avec \(m\) et avec \(m-1\), donc avec leur produit.

Ainsi \(2m-1\) ne peut diviser \(m(m-1)\) que si \(2m-1=1\), ce qui donne \(m=1\), soit \(N=2\), mais \(N\ge 4\). Donc impossible.

Donc \(N/2\) n'est pas \(N\)-décomposable.

B.6.

Pour tout \(N\ge 3\), le nombre d'entiers \(N\)-décomposables est pair.

D'après B.4, si \(k\) est \(N\)-décomposable, alors \(N-k\) l'est aussi.

De plus, \(k\) et \(N-k\) sont distincts sauf si \(k = N-k\) soit \(k = N/2\).

Or d'après B.5, si \(N\) est pair et \(\ge 4\), \(N/2\) n'est pas \(N\)-décomposable.

Si \(N\) est impair, \(N/2\) n'est pas entier, donc pas de point fixe.

Donc les entiers \(N\)-décomposables se regroupent par paires \(\{k, N-k\}\).

Il faut aussi vérifier que 0 et \(N\) sont toujours décomposables (d'après A.3, \(N\) l'est, et 0 l'est trivialement).

0 et \(N\) forment une paire \(\{0,N\}\). Donc le nombre total est pair.

B.7.

Si \(N-1\) est premier, déterminer tous les entiers \(N\)-décomposables.

Soit \(p = N-1\) premier. Alors \(N = p+1\).

La condition pour \(k\) est : \(p\) divise \(k(k-1)\) et \(0\le k\le p+1\).

Comme \(p\) est premier, \(p\) divise \(k(k-1)\) ssi \(p\) divise \(k\) ou \(p\) divise \(k-1\).

Donc \(k \equiv 0 \mod p\) ou \(k \equiv 1 \mod p\).

Avec \(0\le k\le p+1\), les possibilités sont :

• \(k=0\) (car \(0\equiv 0\))

• \(k=p\) (car \(p\equiv 0\))

• \(k=1\) (car \(1\equiv 1\))

• \(k=p+1\) (car \(p+1\equiv 1\))

Donc les entiers \(N\)-décomposables sont \(\{0,1,p,p+1\} = \{0,1,N-1,N\}\).

B.8.

Pour \(k\ge 2\) fixé, montrer qu'il n'existe qu'un nombre fini de \(N\) tels que \(k\) soit \(N\)-décomposable.

La condition est : \(N-1\) divise \(k(k-1)\) et \(k\le N\).

Soit \(d = k(k-1)\). Alors \(N-1\) doit être un diviseur de \(d\).

Les diviseurs de \(d\) sont en nombre fini. Pour chaque diviseur \(d'\) de \(d\), on a \(N = d'+1\).

De plus, il faut \(k\le N\), soit \(k\le d'+1\), ce qui est vrai pour les grands diviseurs, mais peut éliminer certains petits.

Comme il y a un nombre fini de diviseurs, il y a un nombre fini de \(N\) possibles.