Une équation avec l'indicatrice d'Euler
dans Arithmétique
Quelqu'un sait-il si l'équation suivante a des solutions $$\varphi(x)+\varphi(y)=\varphi(4x+3y),$$ où $\varphi$ est l'indicatrice d'Euler ?
Réponses
-
Pas de solution pour $x,y<10\,000$ sauf $(0,0)$.
-
$\varphi$ n'est pas définie en $0$.
-
Pour Sage, euler_phi(0)=0.
-
Il a écrit quel bouquin Sage ? Parce que dans mes bouquins $\varphi$ n'est pas définie en $0$.
-
Le nombre de générateurs de $\mathbb Z / 0 \mathbb Z$ c'est 1 non?
-
Peut-être, toujours est-il que ce n'est pas la définition que je vois dans mes livres ou encore sur wikipédia. Mais certes, ça peut se définir en $0$, je l'ai juste jamais vu. Je ne pense donc pas que Breyer a fait un oubli en ne parlant pas de solution non nulle.
-
Que veux-tu que je te dise ?Sagemath a écrit:Return the value of the Euler phi function on the integer n. We defined this to be the number of positive integers <= n that are relatively prime to n. Thus if n<=0 then "euler_phi(n)" is defined and equals 0.
-
En première analyse, moi je lis un livre pour connaître les définitions, et pas un programme. Voilà qu'avec Sage cette fonction est même définie avec des valeurs négatives ...
-
Merci cela semble confirmer qu'il n'y en a pas.
-
Écoute, je te dis ce que dit Sage parce que c'est Sage qui a donné la solution $(0,0)$ qui t'étonne. Mon but n'est pas de révéler une vérité universelle mais d'expliquer pourquoi la réponse $(0,0)$ est sortie du script idiot que j'ai fait tourner.
Dans le même genre, il est assez classique mais pas universel de définir un coefficient binomial $\binom{n}{k}$ par $0$ si l'inégalité $0\le k\le n$ n'est pas satisfaite. Par exemple, l'égalité $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}k$ devient vraie sans hypothèse.
Toutefois, ce n'est pas la seule façon : il est parfois plus futé de définir $\binom{a}{k}=\frac{a(a-1)\cdots(a-k+1)}{k!}$ pour tout $a$ et tout entier naturel $k$. Par exemple pour le développement en série de $(1+x)^a$. C'est d'ailleurs ce que fait Sage apparemment... avec encore $\binom{x}{k}=0$ si $k<0$. Dans ce cas, $\binom{-1}k=(-1)^k$ (et pas $0$ comme avant).
Selon dans quel livre on va chercher cette définition étendue des coefficients binomiaux, on ne trouvera pas la même réponse. Alors, où vaut-il mieux aller la chercher ?
PS (rétabli) : On s'ennuie un peu sur le forum, ce soir, non, à pinailler sur cette extension triviale et innocente de la définition ?
Edit : Ce message s'adresse à Skyffer bien sûr. Content d'avoir pu appuyer la conjecture sous-jacente de Breyer, fût-ce sans imagination. -
C'est vrai. On pourrait plutôt se demander pour changer si 1 est premier.
-
Contribution très maigre :-D Si $x=y$ est premier avec $7$ il n'y a pas de solution de manière évidente. Sinon on écrit $x = p_1^{r_1} \dots p_k^{r_k} 7^r$ avec les $p_i$ premiers deux à deux distincts et différents de $7$, $r$ et les $r_i \geq 1$. En éliminant ce qu'il y a en commun, il reste $2\varphi(7^r) = \varphi(7^{r+1})$, c'est-à-dire $127^{r-1}=67^r$, de nouveau absurde. Ça devrait pouvoir se généraliser au cas où $x$ est un diviseur unitaire de $y$ et vice-versa.
Bon je vais me coucher... -
Salut
Après la remarque de @Poirot (c'est quoi le $67$ et le $127$ ?). Les positions de $x$ et $y$ étant symétriques dans le premiers membre de l'égalité. On aurait s'il y a solution: $\varphi(4x + 3y) = \varphi(4y + 3x)$. Or $x\neq y$, $4x + 3y\neq 4y + 3x$, n'ont pas la même décomposition en produit de facteurs premiers, alors $\varphi(4x + 3y)\neq\varphi(4y + 3x)$
N'est pas ?
J'ai un doute.(En tout s'il y a solution, $x$ doit être relativement proche de $y$)
Merci d'avance. -
@babsgueye: oui tu peux douter. Il y a des tas de couples $(x_1,x_2)$ tels que $x_1>x_2$ vérifiant $\varphi(x_1)=\varphi(x_2)$. Voir par exemple la suite A0014197.
-
Merci @Breyer du lien. J'avais un peu vu que ça tient pas: exemple $5$ et $8$ !
Si cMais par ailleurs, si $x\neq y$ les ensembles $(Z/xZ)^*$ et $(Z/yZ)^*$ ont des éléments différents de cardinal $\gt$ $\frac{\max(\varphi(x),\varphi(y)}{2}$.ela est vrai, il ne pourra pas y avoir d'égalité !
Mais qu'est que ça donne avec $x + y$ à la place de $4x + 3y$ ? -
Bonsoir.
Je pense que $\varphi(4x+3y)\geq2(\varphi(x) + \varphi(y))$ et que $\varphi(4x+3y)\neq\varphi(3x+4y)$ pour tout $(x\neq y)$ -
Soit $P_{a,b}$ l'équation $\phi(x)+\phi(y)=\phi(ax+by)$ en $x,y \in \N^*$.
Les équations $P_{3,4}, P_{3,6},P_{3,8}$ n'ont pas de solutions faciles à trouver par ordinateur.
Les équations $P_{3,5}, P_{3,7}$ ont des solutions.
On peut conjecturer que les équations $P_{3,4+2k}$ n'ont pas de solutions et que les équations $P_{3,4+2k+1}$ ont des solutions.
De même, pour $a=4$, les équations $P_{4,6+3k}$ n'ont pas l'air d'avoir de solutions, alors que les équations $P_{4,6+3k+1}$ et $P_{4,6+3k+2}$ en ont (par ordinateur pour les petites valeurs de $k \in \N$). -
Merci Marco pour cette exploration. C'est intéressant. On peut ajouter semble-t-il que pour $k>0$, $P_{1,k}$ $P_{2,k}$ ont des solutions ainsi que $P_{3,3}$. $P_{3,4}$ est donc la première équation qui n'en aurait pas.
-
Voici les solutions pour $P_{a,b}$ avec $a=3,4$, et $2(a-1)<b<40$ et $b \neq 0 \pmod{a-1}$. Il n'y a que la solution de $P_{4,35}$ qui est manquante.
a,b : x y
3,5 : 23 3
3,7 : 23 3
3,9 : 31 3
3,11 : 163 9
3,13 : 47 3
3,15 : 83 3
3,17 : 139 9
3,19 : 71 3
3,21 : 79 3
3,23 : 47 3
3,25 : 239 3
3,27 : 283 9
3,29 : 167 3
3,31 : 79 3
3,33 : 127 3
3,35 : 1669 21
3,37 : 359 3
3,39 : 683 3
4,7 : 383 4
4,8 : 439 43
4,10 : 1901 25
4,11 : 1189 64
4,13 : 1433 16
4,14 : 797 8
4,16 : 479 4
4,17 : 3037 76
4,19 : 191 4
4,20 : 5701 61
4,22 : 857 16
4,23 : 1903 16
4,25 : 8609 64
4,26 : 1709 44
4,28 : 2549 13
4,29 : 12277 28
4,31 : 7321 146
4,32 : 1423 19
4,34 : 4891 104
4,37 : 383 4
4,38 : 2449 13 -
On peut montrer que si $x,y \in \N^*$ sont tels que $\phi(x)+\phi(y)=\phi(4x+3y)$, alors $4x+3y$ est divisible par au moins quatre nombres premiers distincts. En effet, si ce n'est pas le cas, $4x+3y$ s'écrit $p^{\alpha}q^{\beta}r^{\gamma}$ ou $p^{\alpha}q^{\beta}$ ou $p^{\alpha}$.
Traitons le premier cas: $4x+3y=p^{\alpha}q^{\beta}r^{\gamma}$.
Si $2<p<q<r$, $\phi(4x+3y)=(4x+3y)(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})\geq (4x+3y)\frac{2}{3}\frac{4}{5}\frac{6}{7}=\frac{64}{35}x +\frac{48}{35}>x-1+y-1\geq \phi(x)+\phi(y)$, donc on obtient une contradiction.
Si $p=2, q=3$ et $r>3$, on a $2 \mid 4x+3y$, donc $2 \mid y$, donc $\phi(y)\leq \frac{y}{2}$.
$3 \mid 4x+3y$, donc $3 \mid x$, donc $\phi(x) \leq \frac{2}{3}x$.
$\phi(4x+3y)\geq (4x+3y)\frac{1}{2}\frac{2}{3}\frac{4}{5}=\frac{16}{15}x+\frac{4}{5}y>\frac{2}{3}x+\frac{y}{2}\geq \phi(x)+\phi(y)$, donc on a une contradiction.
Si $p=2$ et $3<q<r$, ou $p=3$ et $3<q<r$, $\phi(4x+3y)\geq (4x+3y)\frac{1}{2}\frac{4}{5}\frac{6}{7}\geq \frac{96}{70}x+\frac{72}{70}y> \phi(x)+\phi(y)$, donc on a encore une contradiction.
On traite de même les cas: $4x+3y=p^{\alpha}q^{\beta}$ et $4x+3y=p^{\alpha}$. -
Joli résultat. Mais il ne semble pas que ce soit possible d'aller beaucoup plus loin avec cette méthode...
-
On a besoin d’informations sur la décomposition en facteur premier d’une combinaison linéaire de deux entiers naturels non nuls $x$ et $y$ en fonction des décompositions de $x$ et $y$.
En général, ce genre de problème est très compliqué... (Ce qui ne veux pas dire qu’on ne peut pas en trouver une solution simple dans ce cas là). -
J'ai une autre question a priori plus simple: une solution de l'équation $\varphi(x)+\varphi(x-1)=\varphi(2x)$ est-elle toujours paire?
-
Bien sûr, si $x$ est impair, $\phi(2x)=\phi(x)$, donc on ne peut avoir l'égalité, car $\phi(x-1)>0$.
-
Merci Marco ce cas est effectivement "trivial". Sans doute qu'un argument simple marche aussi pour $\varphi(x)+\varphi(x-1)=\varphi(px)$ pour $p\in\{3,5\}$ dont les solutions sont aussi paires. Mais $\varphi(x)+\varphi(x-1)=\varphi(7x)$ n'a a priori pas de solution.
-
Je ne pensais à rien en particulier, mais beaucoup de problèmes dans ce genre sont très difficiles (par exemple la conjecture de Goldbach ou la conjecture ABC).
Comme je l’ai dit, peut-être que ton problème particulier a tout de même une solution élémentaire. -
Tiens les solutions de $\varphi(x)+\varphi(x-1)=\varphi(2x)$, qui sont paires comme l'a montré Marco, semblent vérifier quelque chose de moins trivial pour $x>2$, à savoir qu'elles sont de la forme $6k+4$.
-
Par ordinateur, on peut chercher les triplets $(a,b,c)$ tels que les équations de la forme $\varphi(x)+\varphi(y)=\varphi(ax+by+c)$ n'ont pas de solution.
Soit $1 \leq b<50$ et $0 \leq c < 50$, l'équation $\varphi(x)+\varphi(y)=\varphi(2x+by+c)$ n'a pas de solution en $x,y$, si et seulement si $b$ est multiple de $6$ et $c\equiv 3 \pmod 6$.
(Pour $2x+by+c<100000$) -
@ Marco: Cela montre à mon avis qu'il doit y avoir des règles arithmétiques accessibles gouvernant ces équations.
En continuant de jouer avec ces équations j'ai émis deux petites conjectures liées à des familles particulières de nombres premiers.
Conjecture 1
Les seules solutions de l'équation $$\varphi(x)+\varphi(x-1)=\left\lfloor \frac{3x-2}{2}\right\rfloor
$$ sont les nombres premiers de la forme $x=2^{u}+1$ (c'est-à-dire $2$ et les nombres premiers de Fermat).
Conjecture 2
Les seules solutions $\geq7$ de l'équation $$\varphi(x)+\varphi(x-1)=\left\lfloor \frac{4x-3}{3}\right\rfloor
$$ sont les nombres premiers de la forme $x=2^{u}3^{v}+1$. -
Est-ce que tu as remarqué d'autres conjectures pour les nombres premiers de la forme $2^{\alpha_1}3^{\alpha_2}\dots p_k^{\alpha_k}+1$ (où $2,3, \dots ,p_k$ sont des nombres premiers particuliers) ?
-
Salut.
Je rencontre la conjecture suivante: ''$\forall n \gt 0, \, \exists\, m \neq n\, /\, \phi (n) = \phi (m)$''
On sait que: $\phi (2x) = \phi (x)$ si $x$ impair; donc la conjecture est vérifiée pour $n = x \,\text{ou} \, n = 2x \,\text{avec} \, x \,\text{impair}$
On sait aussi que $\phi (2x) = 2\phi (x)$ si $x$ pair.
Je démontre ici que la conjecture est aussi vraie pour $n = 4x \,\text{avec}\, x = \prod_{i=1}^{r}p_{i}^{r_{i}} \,\text{impair, contenant un facteur $p_{k} = 1 + 2^{a}q_{k}$ de degré un tel que $1 + 2^{a-1}q_{k}$ n'est pas un facteur de $x$}$.
En effet, on a $\phi (4x) = 2\phi (2x) = 2\phi (x) = 2\phi (\prod_{i=1}^{r}p_{i}^{r_{i}}) = 2\prod_{i=1,i\neq k}^{r}(p_{i} - 1)p_{i}^{r_{i}-1}2^{a}q_{k}$.
Je pose $m = 8\prod_{i=1}^{r}\dfrac{p_{i}^{r_{i}}}{p_{k}}(1 + 2^{a-1}q_{k})$.
Alors $m\neq n$ et
$\phi (m) = 4\phi (\prod_{i=1, i\neq k}^{r}p_{i}^{r_{i}}(1 + 2^{a-1}q_{k}) = 4\prod_{i=1, i\neq k}^{r}(p_{i} - 1)p_{i}^{r_{i}-1}2^{a-1}q_{k} = \phi (n)$.
Ce que je voulais démontrer.
Cordialement. -
Bonjour.
On peut généraliser le résultat précédent à: $n = 2^{s}x$ avec les mèmes hypothèses sur $x$ et prendre $$m = 2^{(s+1)}\prod_{i=1}^{r}\dfrac{p_{i}^{r_{i}}}{p_{k}}(1 + 2^{(a-1)}q_{k})$$
On a effectivement $n\neq m$ et $\phi (n) = \phi (m)$.
Cordialement. -
La formule\[m = 2^{(s+1)}\prod_{i=1}^{r}\dfrac{p_{i}^{r_{i}}}{p_{k}}(1 + 2^{(a-1)}q_{k})\]est suspecte : comme il y a un $p_k$ en dénominateur dans chaque facteur, il y a un $p_k^r$ dans le dénominateur de $m$ qui n'est donc pas un entier a priori (sauf si $r_k\ge r$).
-
Lire le post précédent. J'ai dit sur les hypothèses sur $x$, que $p_k$ est un facteur de degré 1 ie $r_{k} = 1$. (qui s'écrit sous la forme $1 + 2^{a}q_{k}$).
-
Alors, $m$ n'est pas un entier ! Pas facile de calculer son indicatrice d'Euler.
Tu pourrais donner un exemple numérique de ce que tu écris, en détaillant précisément $r$, les $r_i$, $k$ etc. ? -
Un cas simple: on a $52 = 2^2\times{13}$; $p_k = 13, r_k = 1\,\text{comme toujours}, q_k = 3 \,\text{et}\, a = 2$
on a $2^3\times\dfrac{13}{13}(1 + 2^{(2-1)}\times{3} = 8\times{7} = 56$ et $\phi (52) = \phi (56) = 24$
Regarde encore.
Merci. -
Quel intérêt d'appeler $k$ le nombre $1$ ?
Un exemple un peu moins simple avec $r\ge2$ (au moins deux facteurs impairs) stp ? -
C'est pas $k$ qui est égal à $1$. C'est un $r_k$ qui est égal à $1$, pour $1\leq k\leq r$.
Toi aussi après avoir compris la démo, cherche un contre-exemple de ton coté.
Merci. -
Si j'utilise les notations de ce message, on a $n=52$, $r=1$, $p_1=13$, nécessairement $k=1$. Pour voir l'incongruité de la définition de $m$, il faudrait un exemple avec au moins deux facteurs premiers impairs.
-
Salut @Math Coss, excuse du temps mis à répondre....!
En fait il y a une hypothèse qui manque sur le nombre $x$ et particulièrement sur le facteur $p_k = 1 + 2^{a}q_k$, qui est d'exposant $1$. Il faut que $1 + 2^{(a-1)}q_k$ soit premier.
Je donne un exemple qui illustre cela. Prenons $n = 2^5\times 3^3 \times 7^2 \times23 \times5 = 32.27.49.23.5 = 4 868 640$ et $m = 2^6\times 3^3 \times 7^2 \times23 \times 3\, \text{parce que $5 = 1+2.2$ et on prend donc $3 = 1+2$ à la place de $5$}$. Et alors $m = 64.27.49.23.3 = 5 842 368 \neq n$.
Et pourtant $\phi (n) = 2^4\times 2\times 3^2\times 6\times 7`\times 22\times 4 = 2^9\times 3^3\times 7`\times 11 = 1 064 448$ et $$\phi (m) = 2^5\times 2\times 3^2\times 6\times 7`\times 22\times 2 = 2^9\times 3^3\times 7`\times 11 = \phi (n)$$
Par contre si on avait choisi $23$ au lieu de $5$ comme $p_k$, on aurait pas l'égalité $\phi (n) = \phi (m)$ avec le $m$ qu'on récupère parce que $23 = 1 + 2.11$ et $1 + 11 = 12$ n'est pas premier.
Merci. -
Les calculs dans l'exemple ne sont pas plus convaincants que le cas général :
sage: euler_phi(4868640) 1064448 sage: euler_phi(5842368) 1596672 sage: euler_phi(64*27*49*23*5) 2128896
Dans la formule initiale, est-ce que tu veux dire que si [quelques conditions sont remplies], on remplace un des facteurs premiers de $n$, que l'on note $p_k$, par un autre nombre $q_k$ défini par une recette à préciser ???
En tout état de cause, ce n'est pas ce qui est exprimé par un produit $\displaystyle\prod_{i=1}^r\frac{p_i}{p_k}$, qui n'a pas du tout le même sens que $\displaystyle\frac{\prod_{i=1}^rp_i}{p_k}$ (au moins, cette dernière expression définit toujours un entier). -
Pour moi ces deux expressions ont le même sens.
On remplace ce $p_k$ convenable(*) par $(1 + 2^{(a-1)}q_k)$ si $p_k = 1 + 2^{a}q_k$
(*) $(1 + 2^{(a-1)}q_k)$ doit être premier. (c'est ce qui manquait dans les hypothèses) -
Eh bien non, pas du tout, voyons ! Mettons que l'on ait trois nombres $p_1,p_2,p_3$ et un autre nombre fixé $q$ (qui peut être ton $p_k$ par exemple) :
\[\prod_{i=1}^3\frac{p_i}{q}=\frac{p_1}q\times\frac{p_2}q\times\frac{p_3}q=\frac{p_1p_2p_3}{q^3}\quad
\text{et}\quad\frac{\prod_{i=1}^3p_i}q=\frac{p_1p_2p_3}{q}.\]
Par ailleurs, tes exemples numériques sont faux (même le produit est faux). -
Ben moi j'aurais mis des parenthèses $(\dfrac{p_{i}}{q})$ dans le produit. Mais c'est juste un problème de notation et je peux te rejoindre.
Tu dis que mes calcules numériques sont fausses parce que j'ai écrit $m$ deux fois et sur l'un il y a $5$ à la place du $3$ qui est sur la vraie
valeur de $m$ (Je pense que si c'était un effort de compréhension de la démo que tu faisais, tu pourrais rectifier cela de toi-même sans en faire
un cas comme tu fais !). J'irais le modifier. Les calculs numériques ne sont pas faux; il y a une faute de frappe comme ça peut arriver (je suis
pressé par des contraintes sociales: il y a un mariage dans le coin et j'ai pas toujours l'électricité....dis en passant !).
Il y a une forme plus générales du résultat démontré, mais je pense que c'est pas encore la peine que je la poste, du moment que le plus
simple n'est pas encore compris.
Cordialement. -
En remplaçant le $5$ par un $3$ on trouve :
sage: euler_phi(4868640) 1064448 sage: 64*27*49*23*3 5842368 sage: euler_phi(5842368) 1596672
La faute de frappe n'était pas l'erreur la plus embêtante des deux.
À la main :
\begin{align*}
\varphi(m)&=\varphi(5842368)=\varphi(2^6\times3^4\times7^2\times23)\\
&=(2^6-2^5)\times(3^4-3^3)\times(7^2-7)\times(23-1)\\
&=32\times54\times42\times22\\
&=1596672\ne1064448\\
\varphi(m)&\ne\varphi(n).\end{align*} -
Dans mes calculs j'ai pas $3^4$ mais $3^3$.
-
Pardon avec l'autre $3$ c'est $3^4$. Attends je revois ça.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres