[Maths] Marathon de problèmes

Or clairement $\gcd(n^a-1, n^b-1) \not\mid n$, car $\gcd(n^a-1, n) = 1$ (sauf si $n^a-1$ et $n^b-1$ sont premiers entre eux mais cela ne se produit que si $n = 2$ et $a = 1$).

Je n’ai pas compris ton raisonnement. Tu ne veux pas plutôt dire que $n^a - 1$ et $n$ sont premiers entre eux, que donc $n^a-1$ et $n^b$ aussi, et que donc $\gcd(n^a-1, n^b (n^{a-b}-1)) = \gcd(n^a-1, n^{a-b}-1)$ ?

Mais il y a plus simple : $\gcd(n^a-1, n^b-1) = \gcd(n^a-1, n^b-1 - (n^a-1) n^{b-a}) = \gcd(n^a-1, n^{b-a} - 1)$ (on suppose $b≥a$). C’est plutôt dans ce sens que je vois l’algorithme d’Euclide : on commence avec $(x,y)$ et on retire $x$ à $y$ un certain nombre de fois, puis on échange $x$ et $y$ et on recommence.

a. Très facile par récurrence. $gcd(F_0, F_1) = 1$, et si c’est vrai au rang $n$, alors $gcd(F_{n+1}, F_n) = gcd(F_n + F_{n-1}, F_n) = gcd(F_{n-1}, F_n) = 1$ par hypothèse de récurrence sur la dernière égalité.

b. Moins facile, toujours par récurrence.

(je viens de m’apercevoir que j’ai utilisé $m$ et $n$ au lieu de $a$ et $b$, désolé)
On suppose que $n>m$, sans perte de généralité (le cas où $m=n$ est immédiat), et comme $m=0$ est immédiat, on suppose $m \geq 1$. On commence par montrer par récurrence sur $a \geq 1$ que $F_n = F_a \cdot F_{n-a+1} + F_{a-1} \cdot F_{n-a}$.

Pour $a=1$, $F_n = 1 \cdot F_{n} + 0 \cdot F_{n+1}$.
Pour $1 \geq a \geq n - 1$,

D’où la récurrence.

Montrons l’égalité voulue par récurrence sur n (j’aime bien les récurrences). C’est immédiat pour n = 0.

On a pour tout $0 < m < n$, $gcd(F_{n+1}, F_m) = gcd(F_{n+1-m}\cdot F_{m+1} + F_{n+1-m-1}\cdot F_m, F_m) = gcd(F_{n+1-m}\cdot F_{m+1}, F_m)$.

Soit $p$ un diviseur premier de ce pgcd. On sait que $p | F_m$ et $p |F_{n+1-m}\cdot F_{m+1}$. Or $F_m$ et $F_{m+1}$ sont premiers entre eux donc si $p$ divise $F_m$, alors $p$ ne peut pas diviser $F_{m+1}$ donc $p$ divise $F_{n+1-m}$. Par conséquent $gcd(F_{n+1-m}\cdot F_{m+1}, F_m) | gcd(F_{n+1-m}, F_m)$. La divisibilité dans l’autre sens est immédiate, donc $gcd(F_{n+1-m}\cdot F_{m+1}, F_m) = gcd(F_{n+1-m}, F_m)$.

Or par hypothèse de récurrence, comme $n+1-m \leq n$, et $m \leq n$, on a $gcd(F_{n+1-m}, F_m) = F_{gcd(n+1-m, m)}$. Ce qui permet immédiatement de conclure que $gcd(F_{n+1}, F_m) = F_{gcd(n+1, m)}$ et donc de clore la récurrence.

On procède par analyse-synthèse. Soit $(x,y) ∈ G^2$ une solution au problème, c’est-à-dire tels que $xy = g = yx$ et $x^m = 1 = y^n$. Comme $x$ et $y$ commutent, on a $(xy)^a = x^a y^a$. Pour retrouver $x$ à partir de $g = xy$, la stratégie est de trouver un entier $a$ tel que $x^a = x$ et $y^a = 1$. Il faut donc que $a ≡ 1 \mod m$ et $a ≡ 0 \mod n$. L’existence d’un tel $a$ est assurée par le théorème des restes Chinois, car $m$ et $n$ sont premiers entre eux. Symétriquement, il existe $b$ tel que $b ≡ 1 \mod n$ et $b ≡ 0 \mod m$. On doit donc avoir $x = g^a$ et $y = g^b$. Réciproquement, cela donne toujours une solution puisque :

1. $g^a$ et $g^b$ commutent.
2. $a+b ≡ 1 \mod (mn)$ toujours d’après le théorème des restes Chinois. Comme $G$ est d’ordre $mn$, on a $g^{mn} = 1$, et donc $g^a g^b = g^{a+b} = g$.
3. $ma ≡ 0 \mod (mn)$ et $nb ≡ 0 \mod (mn)$, donc $(g^a)^m = 1 = (g^b)^n$.

Supposons qu’il existe $a \in S^1$ tel que $f(a) \neq g(a)$ (si non, alors c’est évident). Sans perte de généralité, supposons $f(a) > g(a)$.

Montrons par l’absurde qu’il existe $b \in S^1$ tel que $f(b) \leq g(b)$. Supposons que $\forall x \in S^1, f(x) > g(x)$ et notons $I$ l’image de $S^1$ par $g$. $I$ étant l’image d’un fermé, borné par une fonction continue, il est lui-même fermé (et borné). Posons $y = \min I$.

Par hypothèse, $\forall x \in S^1, f(x) > g(x) \geq y$, donc $\forall x, f(x) \neq y$ et donc $y \notin \operatorname{Im}(f)$. Ce qui est en contradiction avec l’hypothèse que les deux fonctions ont la même image. On conclut donc que $\exists b \in S^1, f(b) \leq g(b)$.

Ensuite, il suffit de prendre une paramétrisation continue $p: [0, 1] \to S^1$, et si on note $t_a, t_b$ deux antécédents de $a$ et $b$ respectivement, en posant $h = f - g$, d’après le théorème des valeurs intermédiaires sur $h\circ p$ sur l’intervalle $[\min(t_a, t_b), \max(t_a, t_b)]$, on obtient le résultat escompté.

$f$ et $g$ ayant même image, et compacte, quitte à translater et faire une homothétie, on peut supposer qu’elles sont à valeurs (surjectives) dans $[0,1]$.

Maintenant $f$ et $g$ sont définies sur $S^1$, en fait $f,g$ peuvent être vues comme définies sur $[0,1]$ et vérifiant que $f(0)=f(1)$ et $g(0)=g(1)$. Un point $x\in S^1$ vérifiant $f(x)=g(x)$ est aussi un point sur $[0,1]$ vérifiant cette même équation.

Supposons $f(x)\neq g(x)$ alors par continuité $g(x)-f(x)$ doit être strictement positive ou strictement négative. Disons $g(x)-f(x)>0$, auquel cas elle est à valeurs dans $[0,1]$ elle aussi. Maintenant, si $x_1$ vérifie $g(x_1)=0$ (existe par hypothèse) alors $f(x_1)<0$, absurde. Donc il y a une valeur pour laquelle $g(x)=f(x)$.

Soit $X$ un espace connexe, soit $f, g : X→ℝ$ continues et soit $x,y ∈ X$ tel que $f(x) ≥ g(x)$ et $f(y) ≤ g(y)$. Alors il existe $z ∈ X$ tel que $f(z) = g(z)$.
En effet, regardons la fonction continue $(f,g) : X → ℝ^2$. Soit $c : ℝ^2 → \{<,=,>\}$ l’application qui prend $(a,b) ∈ ℝ^2$ et retourne l’unique $R ∈ \{<,=,>\}$ tel que $a R b$. On pose sur $c$ la topologie générée par le fait que $\{<\}$ et $\{>\}$ sont ouverts, rendant ainsi $c$ continue. Si l’image de $c \circ (f,g)$ était incluse dans $\{<,>\}$, alors comme ce dernier espace est discret et par connexité de $X$, l’image serait en fait incluse dans $\{<\}$ ou $\{>\}$. Chaque possibilité est en contradiction avec une hypothèse, donc l’image contient $=$.

Ensuite, pour l’existence de $x$ tel que $f(x) ≥ g(x)$, on peut demander un $x$ tel que $f(x) ≥ \sup(g)$ ou bien tel que $\inf(f) ≥ g(x)$. En faisant de même pour l’existence de $y$ tel que $f(y) ≤ g(y)$, on obtient deux conditions (et leurs symétriques) :

• L’existence de $x,y$ tels que $\DeclareMathOperator{\im}{im}\im(g) ⊆ [f(y), f(x)]$.
• $\max(f) = \max(g)$ (plus la condition que ces maximums existent)

Dans le cas où $X$ est compact, les bornes des images de $f$ et $g$ sont toujours atteintes et on obtient comme généralisations (hypothèses pouvant remplacer $\im(f) = \im(g)$) :

• $\im(g) ⊆ \im(f)$
• $\sup(g) = \sup(f)$