Pagina 1 di 1

$n\mid 2^m+m$

Inviato: 01 nov 2012, 17:12
da Ido Bovski
Sia $n$ un intero positivo. Dimostrare che esiste un intero positivo $m$ tale che $n\mid 2^m+m$.

Re: $n\mid 2^m+m$

Inviato: 01 nov 2012, 22:53
da auron95
Assomiglia molto all'N2 di ammissione al senior di quest'anno.... (lì era $n\mid 2^m-m$)
Penso che la soluzione sia simile, ci penserò su.

Re: $n\mid 2^m+m$

Inviato: 01 nov 2012, 23:13
da Mist
Dimostro anzitutto che $\forall p \in \mathbb{P}, k \in \mathbb{N}, \exists m\in \mathbb{N} : p^k\mid 2^m+m$ (1)

Per $p=2$ basta porre $m=2^k$ e si ha banalmente la tesi.
Per $p\neq 2$ procediamo per induzione su $k$.
Passo base: per $k=1$ è sufficiente che $m=p-1$ e per il teorema di fermat abbiamo che $p\mid 2^{p-1}+p-1$.
Passo induttivo: supponiamo ora che la tesi sia vera $\forall r < k$. La tesi è ora che $\forall r < k \quad \exists x:2^x+x\equiv 0 \pmod{p^r} \quad \rightarrow \quad \exists x:2^x+x\equiv 0 \pmod{p^k}$. Dimostriamo il fatto leggermente più generale per cui $\forall r < k \quad \exists x:2^x\pm x\equiv 0 \pmod{p^r} \quad \rightarrow \quad \exists x:2^x\pm x\equiv 0 \pmod{p^k}$. Mandando ora $x$ in $x+np^{k-1}(p-1)$ si ottiene che $2^{x+np^{k-1}(p-1)}\pm x \pm np^{k-1}(p-1) \equiv 2^x\pm x \mp np^{k-1} \pmod{p^{k}}$
La tesi si riduce ora a dimostrare che esiste un $x$ tale che $2^{x}\pm x \equiv \pm np^{k-1} \pmod{p^k}$. Ma per ipotesi induttiva esiste un $x$ tale che $p^{k-1}\mid 2^{x}\pm x$ e perciò sarà sufficiente porre $\displaystyle n= \frac{2^{x}\pm x}{p^{k-1}}$ per avere un'identità oltre che una congruenza. Si noti che non abbiamo usato da nessuna parte che la base della potenza considerata sia $2$, quindi possiamo concludere che la tesi ottenuta è che $\forall p \in \mathbb{P}, (k,n) \in \mathbb{N}^2,(p,n)= 1, \exists m\in \mathbb{N} : p^k\mid n^m+m$

Una volta quindi dimostrata quindi la tesi sopra è sufficiente dimostrare che $\displaystyle (p_1,\dots ,p_n)\in \mathbb{P}^n: 2^{x_j}+x_j\equiv 0 \pmod{{p_j}^{a_j}} \quad \forall j\in [0,n] \rightarrow \exists H: 2^H+H\equiv 0\pmod{\prod_{j=1}^{n}{p_j}^{a_j}}$
Sia ora $\displaystyle r_i= v_{p_i}\left(\prod_{j\neq i \atop j\in [1,n]}\phi ({p_j}^{a_j}){p_j}^{a_j}\right)$, $\alpha _i$ l'inverso moltiplicativo di $\displaystyle \frac{\prod_{j\neq i \atop j\in [1,n]}\phi ({p_j}^{a_j}){p_j}^{a_j}}{{p_i}^{r_i}}x_i$ modulo ${p_i}^{a_i}$. Sia infine $k_i$ numero naturale coprimo con $p_i$.
Poniamo ora $\displaystyle H= \sum_{i=1}^{n}k_ix_i\frac{\prod_{j\neq i \atop j\in [1,n]}\phi ({p_j}^{a_j}){p_j}^{a_j}}{{p_i}^{r_i}}\alpha _i$ e consideriamo l'espressione modulo ${p_i}^{a_i}$: ad esponente del $2$ tutti gli addendi contenenti un $\phi ( {p_i}^{a_i})$ sono spariti perchè pari da 1 mentre di tutti i termini che non sono ad esponente sopravvivono solo quelli che non hanno tra i loro fattori ${p_i}^{a_i}$. L'equazione si riduce quindi a
$$2^{x_ik_i\frac{\prod_{j\neq i \atop j\in [1,n]}\phi ({p_j}^{a_j}){p_j}^{a_j}}{{p_i}^{r_i}}\alpha _i}+x_ik_i\frac{\prod_{j\neq i \atop j\in [1,n]}\phi ({p_j}^{a_j}){p_j}^{a_j}}{{p_i}^{r_i}}\alpha _i \equiv \left( 2^{\frac{\prod_{j\neq i \atop j\in [1,n]}\phi ({p_j}^{a_j}){p_j}^{a_j}}{{p_i}^{r_i}}\alpha _i}\right) ^{x_ik_i}+k_i \equiv u^{x_ik_i}+k_i \equiv f^{k_i}+k_i \pmod{{p_i}^{a_i}}$$ dove $u$ ed $f$ equivalgono rispettivamente a $\displaystyle \frac{\prod_{j\neq i \atop j\in [1,n]}\phi ({p_j}^{a_j}){p_j}^{a_j}}{{p_i}^{r_i}}\alpha _i $ ed a $u^{x_i}$. Ma "per costruzione" $(f,p_i)=1$ e quindi applicando (1) si ha che tale equazione ammette soluzione in $k_i$. Si ha quindi l'esistenza di $H$ e quindi finalmente la tesi.

Ho fatto probabilmente casino, un errore ci sarà quasi sicuramente e la notazione credo faccia schifo... Spero sia giusta :?

Re: $n\mid 2^m+m$

Inviato: 02 nov 2012, 14:57
da Ido Bovski
Mist ha scritto:la notazione credo faccia schifo
... :|

Non l'ho letta con molta attenzione, ma sembra sia tutto ok :)

Metto nascosto un approccio leggermente alternativo (l'idea poi è sempre quella dell'induzione)
Testo nascosto:
Se $n\mid 2^m+m$ allora, posto $u=m+\varphi(np)v$, riesco a scegliere $v$ tale che $np\mid 2^u+u$, dove $p$ è un primo che divide $n$ o un primo più grande di tutti quelli in $n$. Il caso base non ve lo dico...