Cardinal d'un ensemble
dans Arithmétique
Bonjour
Soit $n$ un entier naturel et soit $a$ un diviseur de $n$ ...quel est le cardinal du plus grand ensemble ( au sens de l'inclusion ) des nombres inférieurs à $n$, qui sont premiers avec $n$ et dont la différence de chaque couple de nombres dans cet ensemble n'est pas un multiple de $a$
Merci pour vos réponses.
Soit $n$ un entier naturel et soit $a$ un diviseur de $n$ ...quel est le cardinal du plus grand ensemble ( au sens de l'inclusion ) des nombres inférieurs à $n$, qui sont premiers avec $n$ et dont la différence de chaque couple de nombres dans cet ensemble n'est pas un multiple de $a$
Merci pour vos réponses.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
La réponse me paraît être $\varphi (a)$ où $\varphi$ est la fonction indicatrice d'Euler.
Notations: $\mathcal E =\Big\{ E\subset [\![1;n]\!] \mid \forall x,y \in E,\:\: x\wedge n =1, \:x\neq y \implies x\not\equiv y \mod a \Big \}.$$\quad \forall E \in \mathcal E,\:\: \forall k \in [\![0;a-1]\!], \:\: E_k = E \cap (a\Z+ k)$,
$\forall m \in \N^*, \: \text{rad}(m)\:\text{désigne le produit des nombres premiers qui divisent} \:m.$
Soit $E \in \mathcal E.\;\;$ $ \forall k \in [\![0;a-1]\!],\:\: \#E_k \leqslant 1.\:\:$ De plus, si $k\wedge a \neq 1,\:$ alors: $ \:\:\#E_k =0.\quad$ Ainsi: $\:\:\#E = \displaystyle \sum_{k=0}^{a-1}\#E_k\qquad\boxed{ \#E \leqslant \varphi (a).}$
Il reste à prouver l'existence d'un élément $F$ de $ \mathcal E$ de cardinal $\varphi(a).$
$\exists ! (a_1,b) \in \N^2 $ tel que $n =a_1b, \:\: \text{rad}(a_1)= \text{rad}(a), \:\:\: a_1 \wedge b =1.\quad$ Alors: $a \wedge b =1.$
Soit $ k \in [\![1;a-1]\!], \:\: k \wedge a =1.\:\:\:\quad \exists q_k \in [\![0;b-1]\!]$ tel que $q_ka+ k \equiv 1 \mod b.\quad$ Ainsi:$$(q_ka+ k)\wedge a_1 =(q_ka+ k)\wedge b =(q_ka+ k) \wedge n= 1.$$
Soit $F = \{ q_ka+ k \mid 0<k<a;\:k \wedge a =1 \} \qquad \boxed {\#F = \varphi(a), \:\:\: F \in \mathcal E.}$