Pseudoprimo d'eulero e pseudoprimo forte.

[dustofstar]

Ciao a tutti! Ho alcuni dubbi sulla dimostrazione del seguente problema..
Devo dimostrare che se $n=3 mod4$ allora se n è uno pseudoprimo di eulero in base b allora è anche uno pseudoprimo forte in base b.
Allora.. Per dimostrare che è uno pseudoprimo forte in base b devo dimostrare che
$b^t=1 mod(n)$
La dimostrazione..dalle dispense di un prof.. mi dice che
volendo scrivere n come $n= 2^s t -1$ .. se $n=3 mod 4 $ allora $s=1$ e quindi $t=(n-1)/2$
Quindi
$b^t=1modn <=> b^((n-1)/2)= 1 mod n$ che è vero in quanto n è uno pseudoprimo d'eulero in base b.

I miei dubbi però sono:
1) perchè $s=1$?
2) la definizione di pseudoprimo di eulero non dice che n è uno pseudoprimo di eulero in base b se $b^((n-1)/2)=(b/n)modn$? Perchè allora usiamo $b^((n-1)/2)= 1 mod n$ ??

Qualcuno mi aiuta a capire su che strada devo "muovermi"?

[Lord K]

Per l'esattezza la definizione di pesudoprimo di Eulero è:

$b^((n-1)/2)\equiv +-1(modn)$

e quella di pseudoprimo forte di base $a$ è un numero dispari composto $n$ tale che $n-1=d2^s$ con $d$ dispari dove vale:

$a^d\equiv1(modn)$

oppure:

$a^(d2^r)\equiv -1(modn)$

dove $r=0,...,s-1$, alle volte basta solo la prima delle due. Da qui noti che con le definizioni rispondi al tuo problema.

[dustofstar]

.. uhm.. ma perchè se $n=3mod4$ allora volendo scrivere $n=2d^s-1$ sicuramente sarà $s=1$?? E' questo passaggio che non riesco a capire..

[Lord K]

"dustofstar":.. uhm.. ma perchè se $n=3mod4$ allora volendo scrivere $n=2d^s-1$ sicuramente sarà $s=1$?? E' questo passaggio che non riesco a capire..

E' da trovare $n=2^sd-1$. Siccome $n\equiv 3 mod4 Rightarrow n=4k_0+3 Rightarrow n=4K_1-1 Rightarrow n=2(2k_1+1)-1$

Da qui chiami $d=2k_1+1$ e ci sei!