Exercices d'arithmétique !

[Asymetric]

Tu pourrais préciser ?

Je suis pas trop sûr, cest juste la premiere idée qui m'est venue en tete des que j'ai vu l'exo
soit $ p, q, r,s,t $ 3 entiers.
le probleme revient a dire que
on cherche CNS pour que $ n(n+p)(n+q) = (n+r)(n+s)(n+t) $
ca revient donc a chercher CNS pour que des racines existent pour ce polynome, qui sera d'ailleurs de degré 2

non???

C'est possible, mais si tu trouves quelque chose d'intéressant après, pourquoi pas.

[Asymetric]

Pour remonter un peu, et pour les nouveaux venus qui s'y intéresseront peut-être, voici un nouvel exercice :

Montrer que l'équation dans $ \mathbb{Z}^3 $, $ x^3 + y^3 + z^3 = x^2 + y^2 + z^2 $, possède une infinité de solutions.

[V@J]

SPOILER:

On pourra observer attentivement les triplets du type $ (x,y,z) = (k+2k^3,-k-2k^3,1+2k^2) $

[Asymetric]

SPOILER:

On pourra observer attentivement les couples du type $ (x,y,z) = (k+2k^3,-k-2k^3,1+2k^2) $

Tu parles d'une indication ! C'est quasiment une solution

[Zweig]

Salut,

On peut faire dégager l'une des variable en posant par exemple $ y = -z $. Il nous reste donc à montrer que l'équation $ 2z^2 + x^2 = x^3 $ admet une infinité de solution mais dans ces conditions $ z^2 = \frac{x^2(x-1)}{2} $, donc $ \frac{x-1}{2} $ doit être un carré, i.e, $ x = 2u^2 + 1 $.

Donc pour tout entier u, l'équation admet le triplet $ (2u^2 + 1,\, u(2u^2 + 1),\,-u(2u^2 + 1)) $ comme solution.

[Asymetric]

Pour faire original, voici deux exercices qui donnent un léger lien entre la théorie des automates (ou plutôt des langages) et l'arithmétique, le deuxième est un peu plus difficile.
(PS : pour comprendre les énoncés, il faut quand même avoir fait de la théorie des automates (par exemple en option info MP)).

Exercice 1 : Soit $ A = \{a\} $ un alphabet. Montrer que $ \{a^{n^2} / n \in \mathbb{N}\} $ n'est pas reconnaissable sur $ A $.

Exercice 2 : Montrer que l'ensemble des écritures binaires des nombres premiers n'est pas reconnaissable.

[V@J]

Histoire de remonter ce sujet (je ne sais pas pourquoi cette envie m'a pris soudain ) :

Soit $ A = \{a\} $ un alphabet. Montrer que $ \{a^{n^2} / n \in \mathbb{N}\} $ n'est pas reconnaissable sur A.

SPOILER:

Par lemme de l'étoile : si $ L = \{a^{n^2} / n \in \mathbb{N}\} $ était reconnaissable, il existerait deux entiers $ u \geq v \geq 1 $ tel que $ \forall n \geq u, a^n \in L \Rightarrow \exists w \in \{1,\dots,v\}, a^{n+w} \in L $. Or, on remarque que $ a^{(uv)^2} \in L $, que $ (uv)^2 \geq u $, mais que $ (uv)^2+w \leq (uv)^2+v < (uv)^2+2uv+1 = (uv+1)^2 $ quel que soit $ w \in \{1,\dots,v\} $, et donc que $ a^{(uv)^2+w} \notin L $. Il s'ensuit que $ L $ n'est pas reconnaissable sur $ A $.

Exercice 2 : Montrer que l'ensemble des écritures binaires des nombres premiers n'est pas reconnaissable.

SPOILER:

Toujours par lemme de l'étoile (ou une de ses variantes) : Supposons que l'ensemble $ P $ des écritures binaires des nombres premiers soit reconnaissable. Alors il existe un entier $ N \geq 1 $ tel que, pour tous mots $ u, v, w $ tels que $ uvw \in P $ et $ |v| \geq n $, on peut factoriser $ v $ sous la forme $ v = v_1v_2v_3 $ avec $ v_2 \neq \varepsilon $ et $ \forall k \in \mathbb{N}, uv_1v_2^kv_3w \in P $. Considérons alors un facteur premier $ p $ de $ 2^{2^N}+1 $. Notons que $ p \geq 3 $. On sait que $ 2 $ est d'ordre $ 2^{N+1} $ dans $ \mathbb{F}_p $, donc $ p \equiv 1[2^{N+1}] $, et sa représentation binaire s'écrit $ u0^{N}1 $. On en déduit donc qu'il existe $ l \in \{1,\dots,N\} $ tel que $ u0^{N+kl}1 \in P $ pour tout $ k \in \mathbb{N} $ ; c'est-à-dire que $ 2^{kl}(p-1)+1 $ est toujours un nombre premier. Or, si on prend $ k = p-1 $, on sait que $ 2^{kl}(p-1)+1 \equiv -\left(2^{p-1}\right)^l+1 \equiv -1^l+1 \equiv 0 [p] $. Puisque $ 2^{(p-1)l}(p-1)+1 \geq 4(p-1)+1 = 4p-3 > p $, il s'ensuit que $ 2^{(p-1)l}(p-1)+1 $ est en fait composé, ce qui contredit notre supposition initiale. D'où le résultat.

[Asymetric]

Lol
Bon en tout cas, moi je m'en souviens plus des solutions que j'avais trouvé pour ces deux exos, et je t'avoue que je n'ai pas très envie de les rechercher à nouveau, donc je te fais confiance

Bon bah maintenant je ne sais pas quel topic garder entre celui là et l'autre...

[Datkstaw]

.