Teorema B : (Mp+p1-1)/d = p1

Teorema B : (Mp+p-1)/d = p

Come visto nel blog precedente, il Teorema B dà solo condizioni necessarie e non è efficace per la primalità di Mp, ma solo di p. Possiamo dimostrare questo? si.

Il Piccolo Teorema di Fermat afferma che se p è primo allora deve poter dividere 2^(p-1)-1. Siamo in queste condizioni? Vediamo.

Mp + p - 1 = p*d (1)

2^p - 1 + p -1 = p *d

2^p = p*d -p + 2

moltiplichiamo e dividiamo per 2 entrambi i membri:
2/2 * 2^p = 2/2(p*d-p) + 2/2*2

2* 2^(p-1) = 2/2(p*d-p) + 2/2*2

sposto a sinistra il termine 2/2*2 = 2

2*(2^(p-1)-1) = p*d - p

divido per p e per 2

(2^(p-1)-1)/p = (d-1)/2 (2)

Ovvero siamo nella condizioni del Piccolo Teorema di Fermat.

Facciamo un esempio:

2^37-1 con tale tecnica riusciamo a dire solo che 37 è primo; infatti:

2^36-1/37 = 1857283155
n= (2^(p-1)+p-1)/p=3714566311
(n-1)/2 = 1857283155

La (2), che ingloba il significato del Piccolo Teorema di Fermat, è ricavata dalla (1); per cui il Teorema B ci porta solo a dire che l'esponente di Mp è primo.

Perchè il Teorema A è vero
Abbiamo visto nel blog precedente che Mp + 2 = p2*p3 in generale con Mp = 2^p1-1

Il che è equivalente al fatto che:

(2^p1+1)/p2 =p3

Ora 2^p1+1 è primo se p1=2k; poichè p1 lo stiamo ipotizzando numero primo allora 2^p1+1 è composto; Es: 2^3+1=9 2^5+1=33 2^7+1=129 etc

Per essere composto può essere:
p1=4k+1 con k pari ma potenza dispari di 2 (k=2^1, k=2^3 etc)
es: 4*2+1=9, 4*2^3+1=33
p1=4k+3 con k>1 e dispari e multiplo di 3 (k=3,6,9etc)

Da quello di sopra si vede che un divisore p2 di 2^p1+1 è proprio p2=3; difatti ogni
(2^p1+1)%9 = 3 oppure 6 se p1>3.

Se p2=3, allora p3 è un primo? Sì, perchè è vero anche che:

(2^p1+1)/p3 = p2

English version

Theorem B: (mp + p-1) / d = p

As seen in previous blog Theorem B gives only necessary conditions, and is not effective for the primality of Mp, but only by p. We can prove this? yes.

The Fermat's little theorem states that if p is prime then must divide 2 ^ (p-1) -1. We are in these conditions? Let's see.

Mp + p - 1 = p * d (1)
2 ^ p - 1 + p -1 = p * d
2 ^ p = p * d-p + 2

I multiply and divide by 2 both sides: 2 / 2 * 2 ^ p = 2 / 2 (p * d-p) + 2 / 2 * 2
2 * 2 ^ (p-1) = 2 / 2 (p * d-p) + 2 / 2 * 2

I move left the term 2 / 2 * 2 = 2
2 * (2 ^ (p-1) -1) = p*d - p

I divided by p and 2
(2 ^ (p-1) -1) / p = (d-1) / 2 (2)

Now we are in terms of Fermat's little theorem.

For example:
2 ^ 37-1 with this technique we can only say that 37 is prime, because:
2 ^ 36-1/37 = 1857283155
n = (2 ^ (p-1) + p-1) / p = 3714566311
(n-1) / 2 = 1857283155

The (2), which incorporates the significance of Fermat's little theorem, is obtained from (1) and hence Theorem B leads only to say that the exponent of Mp is prime.

Why Theorem A is true?
We saw in the previous blog that Mp + 2 = p2 * p3 in general with Mp = 2 ^ p1-1

Which is equivalent to the fact that:

(2 ^ p1 +1) / p2 = p3

Now 2 ^ p1 +1 is a prime number if p1 = 2k; but if p1 is a prime number then 2 ^ p1 +1 is composite. Ex: 2 ^ 3 +1 = 9 2 ^ 5 +1 = 33 2 ^ 7 +1 = 129 etc

So it must be:
p1=4k+1 with k even but odd power of 2 (k=2^1, k=2^3 etc)
es: 4*2+1=9, 4*2^3+1=33
p1=4k+3 with k>1 and odd, multiple of 3 (k=3,6,9 etc)

So a divisor of 2 ^ p1 +1 is p2 = 3; infact each (2 ^ p1 +1)% 9 = 3 or 6 if p1>3.

If p2 = 3, p3 is a prime number? Yes, because it is also true that

(2 ^ p1 +1) / p3 = p2.