Pagina 4 di 33
Inviato: 02 giu 2009, 00:06
da FeddyStra
Gebegb ha scritto:Va bene.
In effetti i calcoli sono brutti, io li ho fatti al pc.
Comunque c=7717503920.
(Più che una metasoluzione, la sua si direbbe una soluzione non costruttiva.)
Anch'io li ho fatti al pc, però mi viene un po' diverso.
Codice: Seleziona tutto
{a, b} = Last@PolynomialExtendedGCD[x^5 + 5, (x + 1)^5 + 5, x];
p = 1/GCD[Sequence @@ CoefficientList[a, x],
Sequence @@ CoefficientList[b, x]]
z = Simplify[p a]
w = Simplify[p b]
z (x^5 + 5) + w ((x + 1)^5 + 5) ==
Simplify[z (x^5 + 5) + w ((x + 1)^5 + 5)]
PrintTemporary[
Row[{ProgressIndicator[Dynamic[i], {1, p}], " ",
Dynamic[N[100 i/p, 2]], "% : " Dynamic[i]}]];
Catch@For[i = 1, i <= p, i++,
If[Mod[i^5 + 5, p] == 0 && Mod[(i + 1)^5 + 5, p] == 0, Throw[i]]]
Row[{"Il primo è p=", p, ", il valore di x è x=", i, "."}]
Inviato: 02 giu 2009, 12:46
da federiko97
Gebegb ha scritto:In effetti i calcoli sono brutti, io li ho fatti al pc.
Comunque c=7717503920.
Ho paura che tu abbia frainteso qualcosa di nuovo... Quel numero che ti viene come c è evidentemente troppo grande...
Per chi come me è del tutto estraneo al mondo della programmazione, sarebbe simpatico se qualche utente dotato di un po' di buon cuore (ad esempio Feddy) postasse il risultato corretto.
Inviato: 02 giu 2009, 13:34
da exodd
il limite di calcolo per excel è 1553=x
oltre mi dà che il mcd è 4...
Inviato: 22 giu 2009, 22:25
da jordan
Visto che nessuno propone nulla..
Problema 17. Trovare tutti le coppie di primi (p,q) tali che $ 2^p+2^q $ è un multiplo di pq.
(Very easy
)
Inviato: 23 giu 2009, 11:14
da exodd
jordan ha scritto:
Problema 17. Trovare tutti le coppie di primi (p,q) tali che $ 2^p+2^q $ è un multiplo di pq.
vediamo se è giusto...
il caso p=q=2 funziona
nel caso p=2 e q dispari si ha
$ 4+2^q=0 (mod 2q) $
$ 2^{q-2}=-1 (mod q) $
$ 4^{q-2}=1 (mod q) $
visto che q-2 è minore di q-1, allora q-2 divide q-1, ma ciò si ha solo se q=3
p=2 q=3
per p=3, abbiamo che
$ 8+2^q=0 (mod3) $
e cioè q pari
nel caso p=q abbiamo
$ 2*2^p=0(mod p*q) $
che è possibile solo se p e q sono entrambi pari
nel caso p e q dispari distinti maggiori di 3, WLOG p>q, si ha che
$ 2^p+2=0 (mod q) $
$ 2^q+2=0 (mod p) $
$ 4^{p-1}=1(mod q) $
$ 4^{q-1}=1(mod p) $
quindi q-1 divide p-1, quindi
$ p-1>=2p-2 $
$ p>=2p-1 $
se raccogliamo all'inizio viene
$ 2^{p-q}=-1(mod pq) $
$ 4^{p-q}=1 (mod p) $
visto che p-q<p>=2p-2q[/tex]
$ 2q-1>=p $
l'unica alternativa è quindi
$ p=2q-1 $
che è impossibile perchè
$ 2^{2q-1}+2^q=2^{q-1}+1=0 (mod pq) $
$ 2^{q-1}=-1 (mod q) $
impossibile
le uniche soluzioni sono
$ (2,2), (2,3), (3,2) $
Inviato: 23 giu 2009, 13:24
da jordan
Proviamo a riscrivere il tutto con un po di ordine
exodd ha scritto:il caso p=q=2 funziona
[...]
per p=3, abbiamo che
$ 8+2^q=0 (mod3) $
e cioè q pari
Questo pezzo in realtà non serve..
exodd ha scritto:(1).nel caso p=q abbiamo
$ 2*2^p=0(mod p*q) $
che è possibile solo se p e q sono entrambi pari
Ok..
exodd ha scritto:(2).nel caso p=2 e q dispari si ha
$ 4+2^q=0 (mod 2q) $
$ 2^{q-2}=-1 (mod q) $
$ 4^{q-2}=1 (mod q) $
visto che q-2 è minore di q-1, allora q-2 divide q-1, ma ciò si ha solo se q=3
p=2 q=3
Potevi anche dire che $ ord_q(2)=2(q-2) \mid \phi(q) $ e in particolare $ ord_q(2) \le \phi(q) \implies q \in \{2,3\} $, ma comunque va bien..
Adesso possiamo assumere wlog 2<q<p:
exodd ha scritto:(3).[...]$ 2^p+2=0 (mod q) $
$ 2^q+2=0 (mod p) $
$ 4^{p-1}=1(mod q) $
$ 4^{q-1}=1(mod p) $
Fin qui ok..
exodd ha scritto:[...]quindi q-1 divide p-1, quindi
$ p-1>=2p-2 $
$ p>=2p-1 $
se raccogliamo all'inizio viene
$ 2^{p-q}=-1(mod pq) $
$ 4^{p-q}=1 (mod p) $
visto che p-q<p>=2p-2q[/tex]
$ 2q-1>=p $
l'unica alternativa è quindi
$ p=2q-1 $
che è impossibile perchè
$ 2^{2q-1}+2^q=2^{q-1}+1=0 (mod pq) $
$ 2^{q-1}=-1 (mod q) $
impossibile [...]
Intanto spunta l'opzione "disabilita HTML nel messaggio" che mi sa ti si è mangiato un pezzo della risposta..poi potresti spiegare meglio tutta questa parte?
Inviato: 23 giu 2009, 16:28
da FeddyStra
federiko97 ha scritto:Per chi come me è del tutto estraneo al mondo della programmazione, sarebbe simpatico se qualche utente dotato di un po' di buon cuore (ad esempio Feddy) postasse il risultato corretto.
L'output del mio programma fornisce p=1968751. Il valore corrispondente di x è x=533360.
Inviato: 23 giu 2009, 17:03
da exodd
ammetto che l'ho scritta molto male...
exodd ha scritto:[...]quindi q-1 divide p-1, quindi
$ p-1>=2q-2 $
$ p>=2q-1 $
EDIT: essendo
$ p-1=a(q-1) $,
con $ a>1 $, abbiamo che
$ p-1>=2q-2 $
$ p>=2q-1 $
se raccogliamo all'inizio viene
$ 2^{p-q}=-1(mod pq) $
$ 4^{p-q}=1 (mod p) $
visto che p-q<p>=p[/tex]
EDIT: abbiamo assunto p>q, quindi
$ 2^p+2^q=2^q(2^{p-q}+1)=0 (mod pq) $
$ 2^{p-q}+1=0 (mod pq) $
$ 2^{p-q}+1=0 (mod p) $
$ 2^{p-q}=-1(mod p) $
$ 4^{p-q}=1 (mod p) $
$ p-q<p-1 $
$ 2p-2q\le{p-1} $
$ p\le{2q-1} $
l'unica alternativa è quindi
$ p=2q-1 $
che è impossibile perchè
$ 2^{2q-1}+2^q=2^{q-1}+1=0 (mod pq) $
$ 2^{q-1}=-1 (mod q) $
impossibile
EDIT:abbiamo, dai 2 passaggi precedenti,
$ 2q-1>=p $
$ p>=2q-1 $
che si verificano contemporaneamente solo per
$ p=2q-1 $
che è impossibile perchè
$ 2^{2q-1}+2^q=2^{q-1}+1=0 (mod pq) $
$ 2^{q-1}=-1 (mod q) $
impossibile per il piccolo teorema di fermat
è strano, ma se scrivo >= al posto di \le, mi accorpa il testo con il rigo di sopra...
Inviato: 23 giu 2009, 18:58
da jordan
Adesso è tutto chiaro, a te il prossimo
Inviato: 23 giu 2009, 23:58
da exodd
problema 18
provare che la somma dei quadrati di 1984 numeri positivi consecutivi non può essere un quadrato perfetto
Inviato: 24 giu 2009, 01:20
da jordan
Soluzione problema 18.
Se $ f(t):=\sum_{i=1}^t{i^2} $ allora $ 64 \mid f(64)-32 \implies 64 \mid (f(x+1984)-f(x))-32 $. In altre parole la valutazione 2- adica di tale somma è sempre dispari.
Inviato: 24 giu 2009, 01:52
da jordan
Problema 19.
Siano fissati degli interi positivi $ a,b,c $. Mostrare che esiste un intero positivo $ x $ tale che $ a^x+x \equiv b \pmod c $.
Inviato: 24 giu 2009, 08:45
da Natalino
jordan ha scritto:Soluzione problema 18.
Se $ f(t):=\sum_{i=1}^t{i^2} $ allora $ 64 \mid f(64)-32. $
Come hai fatto a dire questo? hai usato la formula della somma dei primi quadrati?
jordan ha scritto:
$ \implies 64 \mid (f(x+1984)-f(x))-32 $. In altre parole la valutazione 2- adica di tale somma è sempre dispari.
Non mi sono chiari nemmeno questi due passaggi. Potresti spiegarmeli per favore?
Grazie mille.
Inviato: 24 giu 2009, 13:18
da jordan
Natalino ha scritto:Come hai fatto a dire questo? hai usato la formula della somma dei primi quadrati?
Si
Natalino ha scritto:
jordan ha scritto:
$ \implies 64 \mid (f(x+1984)-f(x))-32 $. In altre parole la valutazione 2- adica di tale somma è sempre dispari.
Non mi sono chiari nemmeno questi due passaggi. Potresti spiegarmeli per favore?
Sei d'accordo che $ f(x+64)-f(x) \equiv f(64) \pmod{64} $ per ogni x intero?
Per cui $ f(x+k\cdot 64)-f(x) \equiv kf(64) \pmod{64} $
Nel nostro caso k=31, che è dispari, per cui $ f(x+1984)-f(x) \equiv 31 \cdot f(64) \equiv 31 \cdot 32 \equiv 32 \pmod{64} $.
Quindi quando conti le potenze di 2 che dividono quella somma ne trovi esattamente 5, che non è pari..
Spero sia più chiaro
Inviato: 24 giu 2009, 14:25
da Natalino
Chiarissimo!! Grazie mille, come al solito
