Staffetta tdn

[FeddyStra]

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, "."}]

[federiko97]

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.

[exodd]

il limite di calcolo per excel è 1553=x
oltre mi dà che il mcd è 4...

[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 )

[exodd]

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) $

[jordan]

Proviamo a riscrivere il tutto con un po di ordine

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..

(1).nel caso p=q abbiamo
$ 2*2^p=0(mod p*q) $
che è possibile solo se p e q sono entrambi pari

Ok..

(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:

(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..

[...]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?

[FeddyStra]

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.

[exodd]

ammetto che l'ho scritta molto male...

[...]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...

[jordan]

Adesso è tutto chiaro, a te il prossimo

[exodd]

problema 18

provare che la somma dei quadrati di 1984 numeri positivi consecutivi non può essere un quadrato perfetto

[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.

[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 $.

[Natalino]

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?

$ \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.

[jordan]

Come hai fatto a dire questo? hai usato la formula della somma dei primi quadrati?

Si

$ \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

[Natalino]

Chiarissimo!! Grazie mille, come al solito