[TdN] Raccolta di problemi #2

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<font color=blue><!-- BBCode Start --><B>Problema 1:</B><!-- BBCode End --></font> sia n un intero positivo. Si dice che n è uno pseudoprimo in base 2 sse n è composto e inoltre: 2<sup>n-1</sup> = 1 mod n. Mostrare che esistono infiniti pseudoprimi in base 2. [risolto da Simo_the_wolf]
<BR>
<BR>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...
<BR>
<BR><font color=blue><!-- BBCode Start --><B>Problema 2:</B><!-- BBCode End --></font> per ogni n intero > 2, siano p<sup>(n)</sup> il più grande numero primo naturale <U><</U> n ed S<sup>(n)</sup> l\'insieme dei totativi di n, ovvero di tutti e soli i numeri interi positivi <U><</U> n e primi con n. Detta d<sup>(n)</sup> la distanza massima fra due elementi consecutivi di S<sup>(n)</sup>, mostrare che risulta: d<sup>(n)</sup> < 2p<sup>(n)</sup>. [risolto da masso]
<BR>
<BR>NdH: in fondo, ^spider^, il problema non era poi così difficile. <IMG SRC="images/forum/icons/icon_smile.gif">
<BR>
<BR><font color=blue><!-- BBCode Start --><B>Problema 3:</B><!-- BBCode End --></font> 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.
<BR>
<BR>NdH: al solito, phi(·) denota qui la funzione dei totienti di Eulero.
<BR>
<BR><font color=blue><!-- BBCode Start --><B>Problema 4:</B><!-- BBCode End --></font> sia f(x) := x<sup>3</sup> + 17, per ogni x € R. Dimostrare che, per ogni n intero > 1, esiste x<sub>n</sub> € N tale che: 3<sup>n</sup> || f(x<sub>n</sub>).
<BR>
<BR>----------------
<BR>
<BR>EDIT: aggiornata la lista dei solutori.<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 30-01-2005 13:15 ]
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

Risolviamo il n°1...
<BR>
<BR>Vogliamo dimostrare che se n è pseudoprimo con 2 allora anche 2<sup>n</sup>-1 è pseudoprimo con 2. Abbiamo che 2<sup>n</sup>-1 è composto in quanto n è composto (ricordiamo che se a|b allora 2<sup>a</sup>-1|2<sup>b</sup>-1 (*) ) e inoltre
<BR>2<sup>(2<sup>n</sup>-1)-1</sup>=2<sup>2(2<sup>n-1</sup>-1)</sup>=2<sup>2jn</sup>==1<sup>2j</sup>==1 (mod 2<sup>n</sup>-1)
<BR>Quindi 2<sup>n</sup>-1 è pseudoprimo con 2.
<BR>Ma 2<sup>n</sup>-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 2<sup>n</sup>-1. Ad esempio 561 è pseudoprimo con 2 (anche perchè è il più piccolo numero di Carmichael...) e costruendo una successione in questo modo:
<BR>x<sub>0</sub>=561
<BR>x<sub>n+1</sub>=2<sup>x<sub>n</sub></sup>-1
<BR>Otteniamo tuttie infiniti (per la crescenza) numeri pseudoprimi con 2.
<BR>
<BR>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 2<sup>k</sup>-1>1 <IMG SRC="images/forum/icons/icon21.gif">
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: Simo_the_wolf il 28-01-2005 22:37 ]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Ok, Simo, abbiamo avuto esattamente la stessa idea dimostrativa! Tuttavia...
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-28 21:43, Simo_the_wolf wrote:
<BR>Risolviamo il n°1 [...] Abbiamo che 2<sup>n</sup>-1 è composto in quanto n è composto
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>...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: 2<sup>n</sup> - 1 > n.
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>Ad esempio 561 è pseudoprimo con 2 (anche perch<!-- BBCode Start --><B>è</B><!-- BBCode End --> è il più piccolo numero di Carmichael...)
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>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 := ord<sub>561</sub>(2). Viste le proprietà del gaussiano: g | m, ove
<BR>m := lcm(phi(3), phi(11), phi(17)) = lcm(2, 2 · 5, 2<sup>4</sup>) =2<sup>4</sup> · 5.
<BR>
<BR>Dico che m divide n-1. Difatti: n - 1 = 3 · 11 · 17 - 1 = 3 · 11 - 1 = 0 mod 2<sup>4</sup>, e sì pure: n-1 = 3 · 11 · 17 - 1 = 3 · 2 - 1 = 0 mod 5, per cui: n-1 = 0 mod 2<sup>4</sup> · 5, ovvero m | n-1, q.e.d. Indi, per transitività: g | n-1, e perciò: 2<sup>n-1</sup> = 1 mod n, essendo gcd(2, n) = 1. Questo conclude la verifica...<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 29-01-2005 13:42 ]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<font color=red><!-- BBCode Start --><B>Problema 5<sup>*</sup>:</B><!-- BBCode End --></font> 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 sum<sub>m=1...+inf</sub> 1/g(m) risulta convergente.
<BR>
<BR>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"> <font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 30-01-2005 01:02 ]
Avatar utente
MASSO
Messaggi: 134
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza\Pisa

Messaggio da MASSO »

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:
<BR>p^(n) > n/2 == > 2p^(n) > n > n-1
<BR>
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-30 12:36, MASSO wrote:
<BR>Problema 2: è noto che tra un numero ed il suo doppio, esiste almeno un numero primo [...]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>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ù...
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

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">
<BR>
<BR>----
<BR>
<BR><font color=blue><!-- BBCode Start --><B>Problema 6:</B><!-- BBCode End --></font> siano a, b, c € Z tali che (a + b + c) | (a<sup>2</sup> + b<sup>2</sup> + c<sup>2</sup>). Mostrare che esistono allora infiniti n € N tali che: (a + b + c) | (a<sup>n</sup> + b<sup>n</sup> + c<sup>n</sup>).<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 30-01-2005 14:14 ]
Bloccato