OliForum Matematico

Problema 1: sia n un intero positivo. Si dice che n è uno pseudoprimo in base 2 sse n è composto e inoltre: 2n-1 = 1 mod n. Mostrare che esistono infiniti pseudoprimi in base 2. [risolto da Simo_the_wolf]
 
 NdH: vorrei invitarvi caldamente ad evitare l\'utilizzo del teorema di Carmichael, come pure la trasposizione letterale del suo proof. Poi fate pure come vi pare...
 
 Problema 2: per ogni n intero > 2, siano p(n) il più grande numero primo naturale < n ed S(n) l\'insieme dei totativi di n, ovvero di tutti e soli i numeri interi positivi < n e primi con n. Detta d(n) la distanza massima fra due elementi consecutivi di S(n), mostrare che risulta: d(n) < 2p(n). [risolto da masso]
 
 NdH: in fondo, ^spider^, il problema non era poi così difficile. <IMG SRC="images/forum/icons/icon_smile.gif">
 
 Problema 3: fissato genericamente un m intero > 0, provare che, se l\'equazione: phi(n) = m, ammette una soluzione in interi positivi, allora necessariamente ne ammette almeno un\'altra distinta dalla prima.
 
 NdH: al solito, phi(·) denota qui la funzione dei totienti di Eulero.
 
 Problema 4: sia f(x) := x3 + 17, per ogni x € R. Dimostrare che, per ogni n intero > 1, esiste xn € N tale che: 3n || f(xn).
 
 ----------------
 
 EDIT: aggiornata la lista dei solutori. [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 30-01-2005 13:15 ]

Risolviamo il n°1...
 
 Vogliamo dimostrare che se n è pseudoprimo con 2 allora anche 2n-1 è pseudoprimo con 2. Abbiamo che 2n-1 è composto in quanto n è composto (ricordiamo che se a|b allora 2a-1|2b-1 (*) ) e inoltre
 2(2n-1)-1=22(2n-1-1)=22jn==12j==1 (mod 2n-1)
 Quindi 2n-1 è pseudoprimo con 2.
 Ma 2n-1>n per n>1 (si fa induttivamente o come vi pare) e quindi si può costruire una serie di infiniti pseudoprimi prendendone uno solo e poi fare ogni volta 2n-1. Ad esempio 561 è pseudoprimo con 2 (anche perchè è il più piccolo numero di Carmichael...) e costruendo una successione in questo modo:
 x0=561
 xn+1=2xn-1
 Otteniamo tuttie infiniti (per la crescenza) numeri pseudoprimi con 2.
 
 P.S.: (*) c\'era da precisare che naturalmente n deve essere per forza dispari quindi n ha per forza un fattore k t.c. n>k>2 e quindi 2k-1>1 <IMG SRC="images/forum/icons/icon21.gif">
 [ Questo Messaggio è stato Modificato da: Simo_the_wolf il 28-01-2005 22:37 ]

Ok, Simo, abbiamo avuto esattamente la stessa idea dimostrativa! Tuttavia...
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2005-01-28 21:43, Simo_the_wolf wrote:
 Risolviamo il n°1 [...] Abbiamo che 2n-1 è composto in quanto n è composto
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 ...giusto pe\' fa\' il pignolo, quell\'è vero se si ammette n > 1 (intero, gh), come del resto vieni ad assumere, poco oltre, per garantirti che sia: 2n - 1 > n.
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 Ad esempio 561 è pseudoprimo con 2 (anche perchè è il più piccolo numero di Carmichael...)
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Ok, aggiungo soltanto una rapida verifica della pseudoprimalità di n = 561. I criteri di divisibilità in base dieci suggeriscono che 561 è divisibile tanto per 3 quanto per 11. Svolgendo il quoziente, si trova per l\'esattezza 561 = 3 · 11 · 17. Sia dunque g := ord561(2). Viste le proprietà del gaussiano: g | m, ove
 m := lcm(phi(3), phi(11), phi(17)) = lcm(2, 2 · 5, 24) =24 · 5.
 
 Dico che m divide n-1. Difatti: n - 1 = 3 · 11 · 17 - 1 = 3 · 11 - 1 = 0 mod 24, e sì pure: n-1 = 3 · 11 · 17 - 1 = 3 · 2 - 1 = 0 mod 5, per cui: n-1 = 0 mod 24 · 5, ovvero m | n-1, q.e.d. Indi, per transitività: g | n-1, e perciò: 2n-1 = 1 mod n, essendo gcd(2, n) = 1. Questo conclude la verifica... [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 29-01-2005 13:42 ]

Problema 5*: per ogni intero b > 1, siano g(1) = 1, g(2) = 2 e g(m) = m · g(n), se m è un intero > 2 ed n è il numero di cifre significative nella rappresentazione b-esimale di m. Determinare i valori di b per i quali la serie summ=1...+inf 1/g(m) risulta convergente.
 
 NdH: il problema è segnato in rosso e asteriscato non perché sia particolarmente difficile, ma semplicemente dacché vi è coinvolta la nozione di serie. Tuttavia, la questione è simpatica, quindi perché non proporvela... Del resto, facile o difficile, pare proprio che il risultato finale non cambi, maaah... <IMG SRC="images/forum/icons/icon_confused.gif"> [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 30-01-2005 01:02 ]

Problema 2: è noto che tra un numero ed il suo doppio, esiste almeno un numero primo; perciò p^(n) deve essere maggiore della metà di n se no non sarebbe il più grande minore di n; ma se è maggiore della metà di n, allora il suo doppio è maggiore di n e la differenza tra due numeri minori di n è al massimo n-1 quindi riasumendo:
 p^(n) > n/2 == > 2p^(n) > n > n-1

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2005-01-30 12:36, MASSO wrote:
 Problema 2: è noto che tra un numero ed il suo doppio, esiste almeno un numero primo [...]
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Essì, il teorema di Chebyshev (fu postulato di Bertrand). Ok, la tua soluzione è impeccabile, masso. Del resto, il problema non è che fosse particolarmente ostico. L\'ho segnato in blu sol perché il risultato di cui sopra, quantunque universalmente noto (o quasi), non possiede un proof essenzialmente elementare, anche se la dimostrazione di Selberg-Erdos si potrebbe spiegare persino ad un fanciullino della scuola materna, pur di avere un numero sufficiente di gessetti e di lavagne su cui gettarla giù...

Ok, rimpiazzo il problema risolto da masso con un altro che ho appena appena depennato dal mio listone personale. Non vorrei che vi venisse a mancare il lavoro, ecco tutto... <IMG SRC="images/forum/icons/icon_razz.gif">
 
 ----
 
 Problema 6: siano a, b, c € Z tali che (a + b + c) | (a2 + b2 + c2). Mostrare che esistono allora infiniti n € N tali che: (a + b + c) | (an + bn + cn). [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 30-01-2005 14:14 ]

OliForum Matematico

[TdN] Raccolta di problemi #2