Pagina 1 di 1

135. $x+y \mid xn^x+ym^y$

Inviato: 13 nov 2012, 15:14
da jordan
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$.

Re: 135. $x+y \mid xn^x+ym^y$

Inviato: 14 nov 2012, 02:47
da Ido Bovski
[edit: baggianata]

Re: 135. $x+y \mid xn^x+ym^y$

Inviato: 14 nov 2012, 14:44
da kalu
Ido 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)}$.
Così costruisci una coppia di interi non più coprimi :roll:
(Scusami, $\text{rad}(n)$ sarebbe il prodotto dei divisori primi di $n$?)

Re: 135. $x+y \mid xn^x+ym^y$

Inviato: 14 nov 2012, 15:08
da Ido Bovski
kalu ha scritto:
Ido 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)}$.
Così costruisci una coppia di interi non più coprimi :roll:
(Scusami, $\text{rad}(n)$ sarebbe il prodotto dei divisori primi di $n$?)
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...
Sì, $\text{rad}(n)$ è il radicale di $n$ ed è esattamente ciò che tu hai detto.

Re: 135. $x+y \mid xn^x+ym^y$

Inviato: 19 nov 2012, 01:04
da jordan
Qualcuno che si fa avanti? Dai che è anche piu' facile del precedente.. :roll:

Re: 135. $x+y \mid xn^x+ym^y$

Inviato: 21 nov 2012, 15:09
da Ido Bovski
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$.

Re: 135. $x+y \mid xn^x+ym^y$

Inviato: 09 dic 2012, 17:52
da jordan
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}$. []