TEN 2007

COM_KUNENA_LIB_BBCODE_QUOTE_NON_EXISTANT_USER ha scritto:

A quanto pare sono solo soletto oggi....

Ho provato a fare l'esercizio 3 del foglio 5, vi posto il punto a) e aspetto qualche anima pia che mi illumini sul significato di ord2(x^2-n)=1 ....
Non ho capito proprio cosa voglia dire, forse perchè sono mancato quando ha spiegato il crivello?BOH! Può essere ord(x^2-n) tutto calcolato modulo 2?

Comunque:

a) x=1+2k (dispari) => (1+2k)^2 - n =4k^2+4k+(1-n) =4k^2+4k-(n-1)

n dispari quindi n-1 sarà pari =>divisibile per due (n-1)=2L:

=2(2k^2+2k-L) (quindi x^2-n è pari)

Sì il ragionamento è corretto,anche a me viene lo stesso.
Per il secondo punto,io credo che quell ord2 ... = 1 voglia dire che l'ordine di x^2-n sia 1 in Z2(*) ...
Ho provato a dimostrarlo così,credo che mi venga pure,però il discorso è che non sono sicuro che vada fatto in questo modo...schoof non l'ha mai detta sta cosa!!

potresti postarla? Almeno avrei qualcosa su lavorare...dal momento che il tempo è nostro nemico e vorrei, a questo punto, ripassare le cose che ho (più o meno)capito...

Grazie Pax!

COM_KUNENA_LIB_BBCODE_QUOTE_NON_EXISTANT_USER ha scritto:

potresti postarla? Almeno avrei qualcosa su lavorare...dal momento che il tempo è nostro nemico e vorrei, a questo punto, ripassare le cose che ho (più o meno)capito...

Grazie Pax!

Molto volentieri,l'avrei postata anche prima,ma purtroppo non ho a portata di mano il mio quaderno con gli esercizi(che l'ho prestato ad un amico mio e me lo restituisce questa sera)...Fa lo stesso se lo posto stasera???

Onestamente non ricordo la dimostrazione,ho una confusione in testa allucinante con tutte ste formule...

Non preoccuparti!!Va bene lo stesso!

OT (per sdrammatizzare): sapete se si trovano ancora biglietti per il derby di stasera?

Good work!

aleefaby ha scritto:

Allora ES 5 foglio 1: ci tento...
Dividiamo il caso in cui n non sia primo e n primo

Caso 1: Se n non è primo lo possiamo scrivere come n=P*Q con P>1 e Q>1 e ovviamente P e Q minori della radice quadrata di n che è minore di (n-1). Scrivo (n-1)!=1*2*.....*P*Q*...*(n-1) . Siccome ho moltiplicato tutti i numeri per P*Q posso scrivere che (P*Q)divide((n-1)!), ma allora posso dire che n divide ((n-1)!). Quindi (n-1)!=0 (mod n) per n non primo.

Caso 2: n primo: Pongo p=n-1 e prendo tutti gli elementi invertibili di Z* di p e dico che: (p-1)!=1*2*....*p-1. Ma essendo Z*p l'insieme dei numeri invertibili (per ogni elemento x di Z* di p ci sarà un altro elemento y in Z*p tale che x*y=1) posso scrivere che (p-1)!=1. Ricordo che p=n-1 e quindi p-1=n-2 scrivo che (n-1)!=1*2*...*(n-2)*(n-1)=1(n-1).
Posso scrivere che (n-1)! mod n=(n-1) mod n=-1 mod n

Ho cercato di essere il più chiara possibile ma non è facile dopo una giornata persa dietro a sti cavoli di esercizi. A proposito qualcuno sa come si risolve l'esercizio 4 del secondo foglio? Io mi ci sono persa

Ciao ciao

ho capito grazie!
Riguardando gli appunti lo aveva fatto alla prima pseudo-esercitazione, l'unica NON facoltativa di un ciclo di 4 pseudo-esercitazioni che avrebbero dovuto preparare ad un compito NON facoltativo!

Qualche anima pia per caso mi potrebbe mandare in privato la 3a pseudo esercitazione per favore?

Esercizio numero 6, Foglio 1

(Numeri di Mersenne) Per ogni numero naturale n, si definisce l'ennesimo numero di Mersenne come M(n)=2^n-1
(a) Fattorizzare M(n) per 1<=n<=12;
(b) Dimostrare: se M(n) è primo, allora n è primo;
(c) Far vedere che il viceversa di (b) non vale.

(a)
M(1) =2^1-1 =1
M(2) =2^2-1 =3
M(3) =2^3-1 =7
M(4) =2^4-1 =15=3*5
M(5) =2^5-1 =31
M(6) =2^6-1 =63=3*21=3^2*7
M(7) =2^7-1 =127
M( =2^8-1 =255=5*55=5^2*11
M(9) =2^9-1 =511=7*73
M(10) =2^10-1 =1023=3*341=3*11*31
M(11) =2^11-1 =2047=23*89
M(12) =2^12-1 =4095=3^2*5*7*13

(la fattorizzazione di M(11) e M(12) li ho calcolati sul computer, ma come si vede anche a mano M(12) ha una fattorizzazione facile, giusto M(11) poteva far perdere un pò di tempo)

(b) M(n) primo implica n primo
Ipotizziamo per assurdo che n non sia primo (ovviamente assumendo la premessa)
Esistono p,q, numeri interi primi tali che n=p*q AND MCD(p,q)=1
M(n)=2^n-1=2^(p*q)-1
Noi sappiamo che dato un numero primo z:
x^(z-1) (mod z) è congruo a 1
e ovviamente
x^z (mod z) è congruo a x
Quindi
M(n)=2^n-1=2^(p*q)-1=(2^q)^p (mod p) è congruo a 2-1=1 (mod p)
equivalentemente
M(n)=2^n-1=2^(p*q)-1=(2^p)^q (mod q) è congruo a 2-1=1 (mod q)
Per il Teorema Cinese del Resto possiamo scrivere che
M(n) è congruo a 1 (mod p*q)
o equivalentemente
M(n)-1=2^n-1-1=2^n-1=2(2^(n-1)-1) è congruo a 0 (mod p*q=n)
Questo significa che n deve dividere 2(2^(n-1)-1)
ora
2(2^(n-1)-1) congruo a 0 (mod n)
se e solo se 2^(n-1) (mod n) è congruo a 1
è vera se e solo se n è primo, incongruo con quanto detto prima
quindi l'assunzione era sbagliata
e quindi abbiamo dimostrato che
M(n) primo implica n primo

(c) dimostrare che n primo implica M(n) primo
basta trovare un controesempio
11 è un numero primo
M(11)=2047 che non è primo e può essere fattorizzato come 2047=23*89