135. $x+y \mid xn^x+ym^y$
135. $x+y \mid xn^x+ym^y$
Siano $m,n$ interi positivi fissati. Mostrare che esistono infinite coppie di interi positivi $(x,y)$ tali che $\text{gcd}(x,y)=1$ e $x+y \mid xn^x+ym^y$.
The only goal of science is the honor of the human spirit.
-
- Messaggi: 232
- Iscritto il: 07 mag 2012, 11:51
Re: 135. $x+y \mid xn^x+ym^y$
[edit: baggianata]
Ultima modifica di Ido Bovski il 14 nov 2012, 15:09, modificato 1 volta in totale.
Re: 135. $x+y \mid xn^x+ym^y$
Così costruisci una coppia di interi non più coprimiIdo Bovski ha scritto:Dimostriamo che se $x+y\mid n^x-m^y$, allora $\displaystyle x(x+y)+y(x+y)=(x+y)^2\mid n^{x(x+y)}-m^{y(x+y)}$.
(Scusami, $\text{rad}(n)$ sarebbe il prodotto dei divisori primi di $n$?)
Pota gnari!
-
- Messaggi: 232
- Iscritto il: 07 mag 2012, 11:51
Re: 135. $x+y \mid xn^x+ym^y$
Vero, dovrò ricordarmi di non risolvere più problemi alle 2 di notte. Beh, a 'sto punto salta tutta la dimostrazione e purtroppo oggi non ho tempo per pensarci su...kalu ha scritto:Così costruisci una coppia di interi non più coprimiIdo Bovski ha scritto:Dimostriamo che se $x+y\mid n^x-m^y$, allora $\displaystyle x(x+y)+y(x+y)=(x+y)^2\mid n^{x(x+y)}-m^{y(x+y)}$.
(Scusami, $\text{rad}(n)$ sarebbe il prodotto dei divisori primi di $n$?)
Sì, $\text{rad}(n)$ è il radicale di $n$ ed è esattamente ciò che tu hai detto.
Re: 135. $x+y \mid xn^x+ym^y$
Qualcuno che si fa avanti? Dai che è anche piu' facile del precedente..
The only goal of science is the honor of the human spirit.
-
- Messaggi: 232
- Iscritto il: 07 mag 2012, 11:51
Re: 135. $x+y \mid xn^x+ym^y$
Vabè, nessuno sembra interessato, dunque avanzo qualche idea (probabilmente inutile), che in realtà erano parte di una dimostrazione che avevo postato il 16 ma che ho cancellato pochi minuti dopo perché accortomi che ci fosse un buco.
Poiché $\gcd(x, x+y)=1$ e $xn^x+ym^y\equiv x(n^x-m^y) \pmod {x+y}$, si ha che $x+y\mid xn^x+ym^y$ sse $x+y\mid n^x-m^y$.
Sia $p$ un numero primo tale che $p\not\mid nm$. Vogliamo scegliere $x$ e $y$ in modo tale che $n^x\equiv m^y \pmod p$, ovvero $x+y=p$.
Sia $g$ un generatore mod $p$ e siano $\alpha, \beta \in(\mathbb{Z}/p\mathbb{Z})^*$ tali che $n\equiv g^{\alpha}$ e $m\equiv g^{\beta} \pmod p$. Si deve quindi avere che $\alpha x\equiv \beta y \pmod {p-1}$, ovvero $x\equiv \beta (\alpha+\beta)^{-1} \pmod {p-1}$.
Se ora dimostro che sono infiniti i $p$ primi per i quali esiste l'inverso di $\alpha+\beta$ modulo $p-1$ avrei finito perché posso scegliere $x\in(\mathbb{Z}/p\mathbb{Z})^*$ e $y$ di conseguenza.
Un paio di note:
-con la scelta così fatta $\gcd(x, y)=\gcd(x, p-x)=1$
-se $g$ è un generatore mod $p$ allora i $g^k$ con $\gcd(k, p-1)=1$ sono tutti e soli i generatori mod $p$, quindi $x\equiv \beta (\alpha+\beta)^{-1} \pmod {p-1}$ qualsiasi sia la scelta del generatore mod $p$.
Poiché $\gcd(x, x+y)=1$ e $xn^x+ym^y\equiv x(n^x-m^y) \pmod {x+y}$, si ha che $x+y\mid xn^x+ym^y$ sse $x+y\mid n^x-m^y$.
Sia $p$ un numero primo tale che $p\not\mid nm$. Vogliamo scegliere $x$ e $y$ in modo tale che $n^x\equiv m^y \pmod p$, ovvero $x+y=p$.
Sia $g$ un generatore mod $p$ e siano $\alpha, \beta \in(\mathbb{Z}/p\mathbb{Z})^*$ tali che $n\equiv g^{\alpha}$ e $m\equiv g^{\beta} \pmod p$. Si deve quindi avere che $\alpha x\equiv \beta y \pmod {p-1}$, ovvero $x\equiv \beta (\alpha+\beta)^{-1} \pmod {p-1}$.
Se ora dimostro che sono infiniti i $p$ primi per i quali esiste l'inverso di $\alpha+\beta$ modulo $p-1$ avrei finito perché posso scegliere $x\in(\mathbb{Z}/p\mathbb{Z})^*$ e $y$ di conseguenza.
Un paio di note:
-con la scelta così fatta $\gcd(x, y)=\gcd(x, p-x)=1$
-se $g$ è un generatore mod $p$ allora i $g^k$ con $\gcd(k, p-1)=1$ sono tutti e soli i generatori mod $p$, quindi $x\equiv \beta (\alpha+\beta)^{-1} \pmod {p-1}$ qualsiasi sia la scelta del generatore mod $p$.
Re: 135. $x+y \mid xn^x+ym^y$
Manco questo non è piaciuto :/
Allora, se $\text{gcd}(m,n)=z>1$ allora è sufficiente scegliere $y\ge 5$ e $x=z^{y-1}-y$, con $\text{gcd}(x,y)=1$. Altrimenti $z=1$: vogliamo mostrare che esistono infiniti primi $p$ tali che $x+y=p$ soddisfano la nostra richiesta, equivalente a $m^xn^{x-1} \equiv 1 \pmod p$. Assumiamo per assurdo che esiste solo un numero finito di primi $p_i$ che dividono $\{m^kn^{k-1}-1\}_{k \in \mathbb{N}_0}$, e sia quest'insieme $\mathcal{P}:=\{p_1,p_2,\ldots,p_w\}$. Fissato un intero $k_0>0$, sia \[ m^{k_0}n^{k_0-1}-1=\prod_{p_i \in \mathcal{P}'}{p_i^{\alpha_i}} \]
dove gli $\alpha_i$ sono strettamente positivi, e $\mathcal{P}' \subseteq \mathcal{P}$. Ora, definito $h_0:=\text{lcm}\{\varphi(p_i^{2\alpha_i})\}_{p_i \in \mathcal{P}'} \cdot \text{lcm}\{\varphi(p_j)\}_{p_j \in \mathcal{P}\setminus \mathcal{P}'}$, abbiamo:
\[ m^{k_0+th_0}n^{k_0+th_0-1}-1=\prod_{p_i \in \mathcal{P}'}{p_i^{\beta_{t,i}}} \]
per qualche intero positivo $\beta_{t,1},\beta_{t,2},\ldots,\beta_{t,w}$ e ogni intero positivo $t$. Ma questo è impossibile perchè $\upsilon_{p_i}(m^{k_0+th_0}n^{k_0+th_0-1}-1)=\alpha_i$ per ogni $p_i \in \mathcal{P}$. []
Allora, se $\text{gcd}(m,n)=z>1$ allora è sufficiente scegliere $y\ge 5$ e $x=z^{y-1}-y$, con $\text{gcd}(x,y)=1$. Altrimenti $z=1$: vogliamo mostrare che esistono infiniti primi $p$ tali che $x+y=p$ soddisfano la nostra richiesta, equivalente a $m^xn^{x-1} \equiv 1 \pmod p$. Assumiamo per assurdo che esiste solo un numero finito di primi $p_i$ che dividono $\{m^kn^{k-1}-1\}_{k \in \mathbb{N}_0}$, e sia quest'insieme $\mathcal{P}:=\{p_1,p_2,\ldots,p_w\}$. Fissato un intero $k_0>0$, sia \[ m^{k_0}n^{k_0-1}-1=\prod_{p_i \in \mathcal{P}'}{p_i^{\alpha_i}} \]
dove gli $\alpha_i$ sono strettamente positivi, e $\mathcal{P}' \subseteq \mathcal{P}$. Ora, definito $h_0:=\text{lcm}\{\varphi(p_i^{2\alpha_i})\}_{p_i \in \mathcal{P}'} \cdot \text{lcm}\{\varphi(p_j)\}_{p_j \in \mathcal{P}\setminus \mathcal{P}'}$, abbiamo:
\[ m^{k_0+th_0}n^{k_0+th_0-1}-1=\prod_{p_i \in \mathcal{P}'}{p_i^{\beta_{t,i}}} \]
per qualche intero positivo $\beta_{t,1},\beta_{t,2},\ldots,\beta_{t,w}$ e ogni intero positivo $t$. Ma questo è impossibile perchè $\upsilon_{p_i}(m^{k_0+th_0}n^{k_0+th_0-1}-1)=\alpha_i$ per ogni $p_i \in \mathcal{P}$. []
The only goal of science is the honor of the human spirit.