Dal Giappone

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
matty96
Messaggi: 343
Iscritto il: 21 apr 2010, 14:30
Località: Matelandia di Calabria (CS)

Dal Giappone

Messaggio da matty96 » 14 mag 2011, 22:24

Sia $f(x)=x^3+17$ .Dimostrare che per ogni naturale $n \geq 2$ esiste un naturale $x$ tale che $f(x)$ è divisibile per $3^n$ ma non per $3^{n+1}$
<<Se avessi pensato (se pensassi) che la matematica è solo tecnica
e non anche cultura generale; solo calcolo e non anche filosofia,
cioè pensiero valido per tutti, non avrei fatto il matematico (non
continuerei a farlo)>> (Lucio Lombardo Radice, Istituzioni di
Algebra Astratta).
Mathforum
$ \displaystyle\zeta(s)=\sum_{n=1}^\infty \frac {1}{n^s} $

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Re: Dal Giappone

Messaggio da Euler » 16 mag 2011, 13:35

Se riesco a dimostrare che almeno uno tra $3^n-17$ e $2\cdot 3^n-17$ è un residuo cubico mod $3^{n+1}$ per ogni n ho banalmente vinto. Innanzitutto mostro che $2\cdot 3^n-17$ residuo cubico mod $3^{n+1}$$\Rightarrow$ $3^n-17$ residuo cubico mod $3^{n+1}$$\Rightarrow$-17 residuo cubico mod $3^{n+1}$; infatti chiamo y il numero il cui cubo è il primo membro e lo scrivo come $3^{n-1}+a$, allora:
$(3^{n-1}+a)^3=3^{3(n-1)}+a^3+3\cdot 3^{2(n-1)}a+3^na^2\equiv a^3+3^n\equiv 2\cdot 3^n-17 ($mod $3^{n+1})$ da cui $3^n-17$ è un residuo cubico. Ora pongo z il numero il cui cubo è congruo a $3^n-17$, faccio la stessa cosa di prima e ottengo che -17 è residuo cubico. Ora dimostro per induzione la tesi:
-passo base: OK (per n=2 e x=-2)
-passo induttivo: suppongo che la tesi valga per n; allora come detto prima -17 è residuo cubico mod $3^n$. Allora per forza uno tra $-17$, $3^n-17$ e $2\cdot 3^n-17$ è residuo cubico mod $3^{n+1}$. Se lo è almeno uno tra gli ultimi 2 ho vinto, altrimenti chiamo k il numero il cui cubo sia congruo a -17 mod mod $3^{n+1}$; ma allora ne emerge che $(3^{n-1}+k)^3$ è congruo a $3^n-17$, da cui la tesi. $\square$
Spero di non essermi perso nei calcoli XD

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Dal Giappone

Messaggio da dario2994 » 16 mag 2011, 15:20

Non ho guardato la soluzione, ma piazzo un bonus:
Sia $p>2$ primo e $a$ intero non divisibile per $p$. Definisco $Q(x)=x^p+a$. Dimostrate che per $n\ge 2$ esiste $x\in\mathbb{Z}$ tale che $\upsilon_p(Q(x))=n$
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

bĕlcōlŏn
Messaggi: 145
Iscritto il: 22 gen 2011, 12:56

Re: Dal Giappone

Messaggio da bĕlcōlŏn » 17 mag 2011, 10:47

dario2994 ha scritto:Non ho guardato la soluzione, ma piazzo un bonus:
Sia $p>2$ primo e $a$ intero non divisibile per $p$. Definisco $Q(x)=x^p+a$. Dimostrate che per $n\ge 2$ esiste $x\in\mathbb{Z}$ tale che $\upsilon_p(Q(x))=n$
Sei sicuro del bonus? Prendi $p=3$ e $a=2$. $Q(x)=x^3+2$ e ora voglio trovare $x$ tale che $3^2 || x^3+2$. Si ha innanzitutto che $x^3+2 \equiv 0 \Rightarrow x \equiv 1 \pmod 3$. Quindi $x=3k+1$ e $(3k+1)^3+2=27k^3+27k^2+9k+3$ che modulo $9$ fa sempre 3 e quindi non può essere. In generale per hai problemi se $p || a^p - a$. Non ho visto per 3 che succede, ma la mia dimostrazione (che devo rivedere, magari oggi pomeriggio la piazzo) usa l'esistenza di un $x$ tale che $p^4||x^p+a$ (e nel problema originale tale $x$ esiste per fortuna e ci sono :) ).

@Euler: quando guardi modulo $3^{n+1}$ al quarto rigo ciò che scrivi è congro a $a^3+3^na^2$ e non $a^3+3^n$.
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Re: Dal Giappone

Messaggio da Euler » 17 mag 2011, 13:35

bĕlcōlŏn ha scritto:@Euler: quando guardi modulo $3^{n+1}$ al quarto rigo ciò che scrivi è congro a $a^3+3^na^2$ e non $a^3+3^n$.
Sì ma dato che a è coprimo con 3 il suo quadrato è congruo a 1 mod 3 e mi interessa questo perchè se lo scrivo come 3k+1 ottengo $a^3+3^n(3k+1)=a^3+3^{n+1}k+3^n\equiv a^3+3^n $(mod $3^{n+1}$)...scusa avrei dovuto essere più chiaro.

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Dal Giappone

Messaggio da dario2994 » 17 mag 2011, 17:44

Ops... sono stato un poco troppo ottimista nel bonus... $n\ge 2$ è chiedere troppo...
Quindi riscrivo e gli piazzo un nome che fa figo:

Bonus che ha gli anni che ha:
Sia $p>2$ primo e $a$ intero non divisibile per $p$. Definisco $Q(x)=x^p-a$. Vale $p^2|Q(a)$.
Dimostrate che per ogni $n\ge 2$ esiste $x\in\mathbb{Z}$ tale che $\upsilon_p(Q(x))=n$.

Bonus che capisce quello che capisce:
Sia $p>2$ primo e $a$ intero non divisibile per $p$. Definisco $Q(x)=x^p-a$. Vale $p||Q(a)$.
Dimostrate che per ogni $x\in\mathbb{Z}$ vale $\upsilon_p(Q(x))\in \{0,1\}$.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

bĕlcōlŏn
Messaggi: 145
Iscritto il: 22 gen 2011, 12:56

Re: Dal Giappone

Messaggio da bĕlcōlŏn » 18 mag 2011, 19:39

@Euler: scusami tu, non mi ero soffermato con attenzione :)

Ora vedo di risolvere il bonus

2) Suppongo $x \neq a \pmod p$. In tal caso si ha che $x^p-a \equiv x-a \neq 0 \pmod p$ e diunque $v_p(x^p-a)=0$.
Se $x \equiv a \pmod p$ si ha $x=a+pk$ per qualche $k \in \mathbb{Z}$. Allora $x^p-a=(a+pk)^p -a \equiv a^p - a \pmod p^2$.
Ma avendosi $p || a^p - a$, si avrà anche $p||x^p-a$ e quindi $v_p(x^p-a)=1$.

1) Nella prima parte mostro che esiste per $n=2$.
Per $n=2$ cerco $k$ tale che $v_p( (a+kp)^p -a) = 2$. Ho che $(a+kp)^p-a \equiv a^p+a^{p-1}kp^2-a \pmod p^3$. So che $p^2|a^p-a$ e sia $\omega$ il numero tale che $a^p-a=\omega p^2$. Nella precedente si ha che $a^p-a+a^{p-1}kp^2 \equiv p^2(\omega + a^{p-1}k) \pmod p^3$. Per fare in modo che valga il divide esattamente basta prendere $k \equiv \dfrac{p-\omega}{a^{p-1}} \pmod p^2$.
Ora mostro che se esiste per $n$ un tale $x$ allora esiste per $n+1$.
Suppongo che per $n$ esista $x_n$ tale che $p^n || x_n^p - a$. Cerco gli $x_{n+1}$ fra i numeri della forma $x_n+kp^{n-1}$.
Sia ha che $x_{n+1}^p-a = (x_n+kp^{n-1})^p-a = x_n^p+x_n^{p-1}kp^n+...-a$. A partire dal secondo termine tutti gli altri contengono almeno $2n-1$ fattori $p$. Se guardo modulo $p^{n+1}$, essendo $2n-1\geq n+1 \forall n\geq 2$, ho che, detto $\alpha$ il numero per cui $x_n^p-a=p^n\alpha$, $x_n^p-a+x_n^{p-1}kp^n \equiv p^n(\alpha+x_n^{p-1}k) \pmod p^{n+1}$. Quindi basta scegliere $k \equiv \dfrac{p-\alpha}{x_n^{p-1}} \pmod p^2$. In tutto ciò bisogna avere l'accortezza che gli $x_i$ non facciano 0 modulo $p$ per poter dividere. Ma questo è ovvio altrimenti si avrebbe $a \equiv 0 \pmod p$.
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Dal Giappone

Messaggio da dario2994 » 18 mag 2011, 22:05

bĕlcōlŏn ha scritto:@Euler: scusami tu, non mi ero soffermato con attenzione :)

Ora vedo di risolvere il bonus

2) Suppongo $x \neq a \pmod p$. In tal caso si ha che $x^p-a \equiv x-a \neq 0 \pmod p$ e diunque $v_p(x^p-a)=0$.
Se $x \equiv a \pmod p$ si ha $x=a+pk$ per qualche $k \in \mathbb{Z}$. Allora $x^p-a=(a+pk)^p -a \equiv a^p - a \pmod p^2$.
Ma avendosi $p || a^p - a$, si avrà anche $p||x^p-a$ e quindi $v_p(x^p-a)=1$.

1) Nella prima parte mostro che esiste per $n=2$.
Per $n=2$ cerco $k$ tale che $v_p( (a+kp)^p -a) = 2$. Ho che $(a+kp)^p-a \equiv a^p+a^{p-1}kp^2-a \pmod p^3$. So che $p^2|a^p-a$ e sia $\omega$ il numero tale che $a^p-a=\omega p^2$. Nella precedente si ha che $a^p-a+a^{p-1}kp^2 \equiv p^2(\omega + a^{p-1}k) \pmod p^3$. Per fare in modo che valga il divide esattamente basta prendere $k \equiv \dfrac{p-\omega}{a^{p-1}} \pmod p^2$.
Ora mostro che se esiste per $n$ un tale $x$ allora esiste per $n+1$.
Suppongo che per $n$ esista $x_n$ tale che $p^n || x_n^p - a$. Cerco gli $x_{n+1}$ fra i numeri della forma $x_n+kp^{n-1}$.
Sia ha che $x_{n+1}^p-a = (x_n+kp^{n-1})^p-a = x_n^p+x_n^{p-1}kp^n+...-a$. A partire dal secondo termine tutti gli altri contengono almeno $2n-1$ fattori $p$. Se guardo modulo $p^{n+1}$, essendo $2n-1\geq n+1 \forall n\geq 2$, ho che, detto $\alpha$ il numero per cui $x_n^p-a=p^n\alpha$, $x_n^p-a+x_n^{p-1}kp^n \equiv p^n(\alpha+x_n^{p-1}k) \pmod p^{n+1}$. Quindi basta scegliere $k \equiv \dfrac{p-\alpha}{x_n^{p-1}} \pmod p^2$. In tutto ciò bisogna avere l'accortezza che gli $x_i$ non facciano 0 modulo $p$ per poter dividere. Ma questo è ovvio altrimenti si avrebbe $a \equiv 0 \pmod p$.
Yeppa, todo giusto (uguale alla mia) :D
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Rispondi