Staffetta tdn

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 » 05 mar 2010, 13:32

$ 2=3^y-7^x $
Analizzo mod4 e noto che $ \displaystyle y $ e $ \displaystyle x $ hanno stessa parità.
$ 7^x-1=3^y-3 $
Ora sfrutto la formula per le progressioni geometriche e ho:
$ \displaystyle \sum_{i=0}^{x-1} 7^i=\sum_{i=0}^{y-2} 3^i $
Noto che, per $ y \geq 2 $ LHS ha meno fattori di RHS.
Quindi posso raccogliere in questo modo:
$ \displaystyle \sum_{i=0}^{x-1} 7^i-3^i=\sum_{i=x}^{y-2} 3^i $
Ma per quanto detto all'inizio RHS ha un numero dispari di addendi, si ha quindi:
$ \displaystyle 4\mid LHS $ ma $ \displaystyle 4\nmid RHS $ impossibile. Rimane quindi il caso $ y-2=x-1=0 $ che porta all'unica soluzione $ y=2 $ e $ \displaystyle x=1 $

Che ne pensate? Ci sono errori?
Ultima modifica di ndp15 il 05 mar 2010, 16:39, modificato 1 volta in totale.

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

Messaggio da dario2994 » 05 mar 2010, 16:20

Mod 4 si ottiene che x,y hanno la parità differente, perciò falla il punto finale ;) .
Comunque gran bella idea... stanno uscendo fuori metodi carini per affrontare le diofantee :)
p.s. gli "elementi" di una somma si chiamano addendi non fattori.
...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

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 » 05 mar 2010, 16:38

dario2994 ha scritto:Mod 4 si ottiene che x,y hanno la parità differente, perciò falla il punto finale ;) .
Comunque gran bella idea... stanno uscendo fuori metodi carini per affrontare le diofantee :)
p.s. gli "elementi" di una somma si chiamano addendi non fattori.
Giusto giusto. Mi sembrava strano una soluzione tutto sommato semplice fosse sfuggita ai vostri occhi esperti.
Grazie per l'averla definita una bella idea; ora non so se portandola avanti si giunge a qualcosa, però si dovrebbe poter svillupare LHS e scriverlo come 4(ROBA) e far vedere che la diofantea ha soluzione solo con ROBA=0
Ripeto che l'idea è praticabile a proprio rischio e pericolo, non porta necessariamente alla soluzione.
Per il p.s. :ora edito, piccola distrazione.

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 06 mar 2010, 21:13

Giusto per non lasciare niente in sospeso risolvo anche il (brutto :lol:) problema di gibo92:
$ \displaystyle~7^n+2^n=16+x^2 $
n > 1, quindi $ \displaystyle~(-1)^n\equiv x^2\pmod 4 $ da cui $ \displaystyle~n=2m $ per qualche m. Supponiamo m > 2: $ \displaystyle~x^2-7^{2m}=4^m-16>0 $, quindi $ \displaystyle~x\ge 7^m+1 $, da cui $ \displaystyle~4^m-16=x^2-7^{2m}\ge 2\cdot 7^m+1 $, assurdo. Quindi $ \displaystyle~m\le 2 $, che dà l'unica soluzione $ \displaystyle~n=4,x=49 $.

Problema 56. Mostrare che per ogni $ ~a \ge b $ interi positivi e $ ~p \in \mathbb{P} \setminus\{2,3\} $ vale: $ ~p^3 \mid \displaystyle \binom{ap}{bp}-\binom{a}{b} $.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 15 mar 2010, 16:18

UP! Vi do ancora 2 giorni poi se nessuno ha qualcosa in contrario metto la soluzione
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

travelsga
Messaggi: 39
Iscritto il: 30 giu 2008, 13:40
Località: Carrara

Messaggio da travelsga » 16 mar 2010, 14:45

Considero $ q(x)=(x-1)(x-2)\cdots (x-(p-1))=x^{p-1}-c_1x^{p-2}+\cdots-c_{p-2}x+c_{p-1} $

Fatto 1: $ c_1\equiv c_2\equiv\cdots\equiv c_{p-2}\equiv 0\pmod p $ e $ c_{p-1}=(p-1)!\equiv -1\pmod p $
Il polinomio $ p(x)=x^{p-1}-1 $ ha le stesse radici in $ \mathbb F_p $ di $ q(x) $, dunque $ r(x)=q(x)-p(x) $ ha le stesse radici di $ q(x) $ e grado $ \le p-2 $,
assurdo in quanto tale polinomio avrebbe più radici in $ \mathbb F_p $ del suo grado , deve necessariamente essere il polinomio nullo;
la tesi si ottiene confrontando i coefficienti di q(x) e p(x).

Fatto 2$ \displaystyle p|\sum_{j=1}^{p-1}{j^k} $ se e soltanto se $ p-1\nmid k $, altrimenti la somma è $ p-1 $ modulo p.
Considero un generatore g modulo p, la somma si riscrive come $ \displaystyle\sum_{j=1}^{p-1}{g^{jk}}\equiv\frac{g^{k(p-1)}-1}{g^k-1}\equiv 0\pmod p $

Fatto 3: $ p^2|c_{p-2} $
$ \displaystyle c_{p-2}=(p-1)!\sum_{j=1}^{p-1}{\frac{1}{j}}\equiv\frac{(p-1)!}{2}\sum_{j=1}^{p-1}{\frac{1}{j}+\frac{1}{p-j}}\equiv\frac{(p-1)!}{2}\sum_{j=1}^{p-1}{\frac{p}{j(p-j)}}\equiv -\frac{p!}{2}\sum_{j=1}^{p-1}{\frac{1}{j^2}} 0\pmod {p^2}\Longleftrightarrow \sum_{j=1}^{p-1}{\frac{1}{j^2}} 0\pmod p $.
Quest'ultima deriva dal Fatto 2.

Corollario $ q(ap)\equiv (p-1)!\pmod {p^3} $
Difatti $ q(ap)=(ap)^{p-1}-c_1(ap)^{p-2}+\cdots+c_{p-3}(ap)^2-c_{p-2}ap+c_{p-1} $, per i Fatti 1 e 3 $ p^3 $ divide tutti i termini tranne $ c_{p-1} $.

Passiamo finalmente al problema...

$ \displaystyle\binom{pa}{pb}=\frac{ap(ap-1)\cdots(ap-(p-1))(a-1)p((a-1)p-1)\cdots((a-b+1)p-(p-1))}{pb(pb-1)\cdots(pb-(p-1))\cdots p(p-1)\cdots 2\cdot 1} $
$ \displaystyle\frac{a(a-1)\cdots(a-b+1)}{b!}\cdot\frac{\prod_{h=a-b+1}^a{q(hp)}}{\prod_{k=1}^b{q(kp)}}\equiv\binom{a}{b}\frac{(p-1)!^b}{(p-1)!^b}\equiv\binom{a}{b}\pmod {p^3} $
che è la tesi.

Se non ci sono errori grossolani (molto probabile dato che ho saltato alcuni passaggi) dovrebbe funzionare

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 16 mar 2010, 19:48

Bene :D Vai pure con il 57!
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

travelsga
Messaggi: 39
Iscritto il: 30 giu 2008, 13:40
Località: Carrara

Messaggio da travelsga » 19 mar 2010, 17:01

Problema 57 Siano dati $ n,k $ interi positivi con $ n\ge k $. Determinare $ \displaystyle gcd\left(\binom{n}{k},\binom{n+1}{k},\cdots,\binom{n+k}{k}\right) $

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

Messaggio da dario2994 » 19 mar 2010, 17:41

Definisco $ $f(n,k)=\frac{n!}{k!} $
Vale:
$ $gcd\left(f(n,k);f(n+1,k)\right)|k\cdot f(n,k-1) $ ***

Il massimo comun divisore da studiare è uguale a (ottenuto moltiplicando per k!):
$ $\frac{gcd\left(f(n,k);f(n+1,k);\dots ;f(n+k,k)\right)}{k!} $
Chiamo G(n,k) il gcd al numeratore.
Se dimostro che G(n,k)|k! unendolo al fatto ovvio k!|G(n,k) ottengo che la frazione vale 1 e perciò anche il gcd da studiare; che è la tesi.
Lo dimostro per induzione su k
Passo base: k=1... risulta ovvio dato che n,n+1 sono sicuramente coprimi.
Passo induttivo: Svolgo il gcd "a coppie" sfruttando *** e poi uso l'ipotesi induttiva:
$ $G(n,k)|gcd(k\cdot f(n,k-1);k\cdot f(n+1,k-1);\dots ;k\cdot f(n+k,k-1))=k\cdot G(n,k-1)=k! $
Che è la tesi

EDIT: non so perchè ma mi pare segata da qualche parte...
...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

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 19 mar 2010, 19:39

Metto anche la mia:
Fissato $ \displaystyle~n $ sia $ \displaystyle~g(j)=\gcd\left(\binom{n}{j},\binom{n+1}{j},\cdots,\binom{n+j}{j}\right) $
Dimostriamo per induzione che $ \displaystyle~g(j)=1 $.
Passo base: $ \displaystyle~g(0)=1 $ poiché $ \displaystyle~\binom{n}{0}=1 $.
Passo induttivo: supponiamo $ \displaystyle~g(j)=1 $ e mostriamo che $ \displaystyle~g(j+1)=1 $ con $ \displaystyle~j+1\le k $.
Poiché $ \displaystyle~\forall i\le j~g(j+1)\mid\binom{n+i+1}{j+1}-\binom{n+i}{j+1}=\binom{n+i}{j} $ (giacché divide ambedue i binomiali) otteniamo $ \displaystyle~g(j+1)\mid g(j) $ da cui la tesi.
dario2994 ha scritto:$ $gcd\left(f(n,k);f(n+1,k)\right)|k\cdot f(n,k-1) $ ***
Ma $ \displaystyle~f(n,k) $ non divide $ \displaystyle~f(n+1,k) $?
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 19 mar 2010, 20:16

dario2994 ha scritto:Definisco $ $f(n,k)=\frac{n!}{k!} $
Vale:
$ $gcd\left(f(n,k);f(n+1,k)\right)|k\cdot f(n,k-1) $ ***
Per come è definito $ f(\cdot,\cdot) $ vale $ f(b,c)\mid f(a,c) $ per ogni $ (a,b,c)\in \mathbb{N}^3 $ tale che $ a\ge b\ge c $. Per cui anche $ f(n,k)\mid f(n+1,k) $, ciò significa che la tua affermazione è vera se e solo se $ f(n+1,k) \mid kf(n,k-1) $ se e solo se $ k^2\mid n+1 $... :?
Il resto non ho finito di leggerlo ma anche quest'altra affermazione non mi pare molto corretta:
dario2994 ha scritto:Il massimo comun divisore da studiare è uguale a (ottenuto moltiplicando per k!):
$ $\frac{gcd\left(f(n,k);f(n+1,k);\dots ;f(n+k,k)\right)}{k!} $
Bye :o
Edit @Kn: bien :wink:
Edit: controllata anche quella di dario2994, bien anche quella :wink:
Ultima modifica di jordan il 19 mar 2010, 20:36, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.

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

Messaggio da dario2994 » 19 mar 2010, 20:24

Ok, sono un pirla, la dimostrazione che ho fatto è probabilmente giusta, ma ho sbagliato a definire f(n,k)... ecco la vera definizione:
$ $ f(n,k)=\frac{n!}{(n-k)!} $
...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

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 19 mar 2010, 22:29

Problema 58. Mostrare che se $ \displaystyle~\frac{x^2+1}{y^2}+4 $ è un quadrato perfetto allora vale 9.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 » 25 mar 2010, 20:34

Siccome è passata una settimana ma l'ho scoperto solo ieri e non ho tempo di ragionarci molto, provo a buttare li qualche idea che non so dove porti:
$ \displaystyle \frac {x^2+1}{y^2}+4=n^2 $
$ \displaystyle x^2-y^2(n^2-4)=-1 $
Che è un'equazione di Pell e cio' dovrebbe essere confortante.
Ad esempio possiamo dire che $ \displaystyle n^2-4 $ deve poter essere scritto come somma di due quadrati, inoltre se, a differenza mia, si conosce come risolvere un'equazione di Pell con il metodo delle frazione continue si potrebbe giungere a qualcosa di interessante.
Analizzando mod4 si ricavano anche informazioni su tutte le variabili.
Spero di essere stato utile..

Jessica92
Messaggi: 34
Iscritto il: 19 mar 2010, 18:08

Messaggio da Jessica92 » 26 mar 2010, 12:33

Vediamo un po cosa esce fuori :oops:

Non so bene quante cose debba definire

Lavoro in $ \mathbb{Z}[\sqrt{d}] $, cioè quell'insieme che ha elementi del tipo $ z=x+y\sqrt{d} $ con $ x,y\in \mathbb{Z} $

Sia $ \bar{z}=x-y\sqrt{d} $ il coniugato di z e sia $ N(z)=z\bar{z}=x^2-dy^2 $ la norma, si dimostra facilmente che norma e coniugato sono moltiplicativi

Lemma 1:
Sia $ $a_0$ $ la più piccola soluzione di $ N(a)=1 $ allora $ N(b)=-1 $ ha soluzioni sse esiste un $ $b$ $ t.c. $ b^2=a_0 $ []

Ora ponendo $ $n>3$ $ prendo l'equazione di Pell

$ N(z)=4 $

La più piccola soluzione è $ $z_0=n+\sqrt{n^2-4}$ $

Fatto 1
Se $ v_1=\frac{z_0^3}{8} $ allora $ N(v)=1 $

Dim
$ $\frac{z_0^3}{8}\frac{\bar{z_0}^3}{8}=1 $ []

Fatto 2
$ $v_1$ $ è la più piccola soluzione di $ N(v)=1 $
con $ v>1 $

Dim
Chiamo $ 1<$v_0$ $ la più piccola soluzione di $ N(v)=1 $

Fatto 2.1
$ v_1<v^3_0 $

Dim
$ \frac{z_0}{2} < v_0 $, infatti $ \frac{z_0}{2}\ne v_0 $
$ \frac{z_0}{2}\notin \mathbb{Z}[\sqrt{n^2-4}] $ poichè $ $n$ $ è dispari e $ \frac{z_0}{2}\leq v_0 $ per la minimalità di $ z_0 $.

Quindi $ v_1=\frac{z^3_0}{8}<v^3_0 $ []

Fatto 2.2
$ v_1\ne v^2_0 $

Dim
Se pongo $ v_1 = v^2 $
Con
$ $v=a+b\sqrt{n^2-4}$ $ e $ $v_1=\frac{n^3-3n}{2}+\frac{n^2-1}{2}\sqrt{n^2-4}$ $

viene un sistema che non ha soluzioni con $ 3<n $

In conclusione $ v_1=v_0 $ []

Applico il Lemma 1 e poichè non esiste $ v^2=v_0 $ l'equazione di Pell $ N(u)=-1 $ non ha soluzioni []

Se $ $n=3$ $

$ x^2-5y^2=-1 $ ha come soluzione minima $ u_0=2+\sqrt{5} $ []

Dovrebbe andare :?
Ultima modifica di Jessica92 il 26 mar 2010, 19:20, modificato 3 volte in totale.

Rispondi