Staffetta tdn

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Messaggio da FeddyStra » 02 giu 2009, 00:06

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, "."}]
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]

Avatar utente
federiko97
Messaggi: 44
Iscritto il: 03 nov 2008, 20:36
Località: Roma

Messaggio da federiko97 » 02 giu 2009, 12:46

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.
Io credo che alcune entità superiori, pur non avendo odore, possano esistere. Esse influenzano le nostre vite in maniera che nessuno scienziato può comprendere.

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd » 02 giu 2009, 13:34

il limite di calcolo per excel è 1553=x
oltre mi dà che il mcd è 4...
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

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

Messaggio da jordan » 22 giu 2009, 22:25

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 :wink: )
The only goal of science is the honor of the human spirit.

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd » 23 giu 2009, 11:14

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) $
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

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

Messaggio da jordan » 23 giu 2009, 13:24

Proviamo a riscrivere il tutto con un po di ordine :roll:
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?
The only goal of science is the honor of the human spirit.

Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Messaggio da FeddyStra » 23 giu 2009, 16:28

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.
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd » 23 giu 2009, 17:03

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...
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

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

Messaggio da jordan » 23 giu 2009, 18:58

Adesso è tutto chiaro, a te il prossimo :wink:
The only goal of science is the honor of the human spirit.

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd » 23 giu 2009, 23:58

problema 18

provare che la somma dei quadrati di 1984 numeri positivi consecutivi non può essere un quadrato perfetto
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

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

Messaggio da jordan » 24 giu 2009, 01:20

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.
The only goal of science is the honor of the human spirit.

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

Messaggio da jordan » 24 giu 2009, 01:52

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 $.
The only goal of science is the honor of the human spirit.

Natalino
Messaggi: 30
Iscritto il: 30 apr 2008, 23:37

Messaggio da Natalino » 24 giu 2009, 08:45

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.

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

Messaggio da jordan » 24 giu 2009, 13:18

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 :wink:
The only goal of science is the honor of the human spirit.

Natalino
Messaggi: 30
Iscritto il: 30 apr 2008, 23:37

Messaggio da Natalino » 24 giu 2009, 14:25

Chiarissimo!! Grazie mille, come al solito :D

Rispondi