Proprietà moltiplicativa degli pseudoprimi

Dato un numero composto e dispari $ n>1 $, se $ n $ è pseudoprimo nelle basi $ b_1 $ e $ b_2 $ allora lo è anche nel prodotto delle basi $ b_1b_2 $ e nel prodotto di una base per l'inverso dell'altra $ b_1 b_2^{-1} $ e $ b_1^{-1} b_2 $.

Questo risultato è una proprietà degli pseudoprimi strettamente legata al concetto di pseudoprimi di Fermat.

Mostra l'esistenza di una struttura moltiplicativa negli pseudoprimi per alcune basi particolari.

A cosa serve?

E' una proprietà utile per trovare nuovi pseudoprimi a partire da quelli noti.

Un esempio pratico

Considero un numero composto dispari maggiore di 1, ad esempio 15

$$ n=15 $$

E' un numero composto $ 15 = 3 \cdot 5 $.

Cerco delle basi $ b $ in cui questo numero è pseudoprimo.

Un numero è pseudoprimo con $ n=15 $ se è relativamente primo e se $ b^{n-1} \equiv 1 \mod n $

$$ b^{15-1} \equiv 1 \mod 15 $$

$$ b^{14} \equiv 1 \mod 15 $$

Per prima cosa elenco i numeri relativamente primi con 15

$$ 1 \ , \ 2 \ , \ 4 \ , \ 7  \ , \ 8  \ , \ 11  \ , \ 13  \ , \ 14    $$

Verifico tra questi quali sono pseudoprimi con 15

$$ 1^{14} \equiv 1 \mod 15 $$

$$ 2^{14} \equiv 4 \mod 15 $$

$$ 4^{14} \equiv 1 \mod 15 $$

$$ 7^{14} \equiv 4 \mod 15 $$

$$ 8^{14} \equiv 4 \mod 15 $$

$$ 11^{14} \equiv 1 \mod 15 $$

$$ 13^{14} \equiv 4 \mod 15 $$

$$ 14^{14} \equiv 1 \mod 15 $$

Quindi, i numeri pseudoprimi con 15 sono 1¹⁴, 4¹⁴, 11¹⁴, 14¹⁴ e le relative basi sono 1, 4, 11, 14

A] Il prodotto delle basi

A questo punto verifico se Il prodotto delle basi è a sua volta un numero pseudoprimo con 15.

$$ 1 \cdot 4 = 4 \equiv 1 \mod 15  $$

$$ 1 \cdot 11 = 11 \equiv 1 \mod 15  $$

$$ 1 \cdot 14 = 14 \equiv 1 \mod 15  $$

$$ 4 \cdot 11 = 44 \equiv 14 \mod 15  $$

$$ 4 \cdot 14 = 56 \equiv 11 \mod 15  $$

$$ 11 \cdot 14 = 154 \equiv 14 \mod 15  $$

Il prodotto delle basi è 1, 11, 14 che sono anche numeri pseudoprimi con 15.

B] Il prodotto di una base per l'inverso dell'altra

Ora verifico se Il prodotto di una base per l'inverso dell'altra (modulo 15) è un numero pseudoprimo con 15.

Per prima cosa trovo l'inverso moltiplicativo delle basi 1, 4, 11, 14 ovvero quei numeri che $ b b^{-1} \equiv 1 \mod 15 $

$$ 1^{-1} = 1 \rightarrow 1 \cdot 1^{-1} = 1 \equiv 1 \mod 15 $$

$$ 4^{-1} = 4 \rightarrow 4 \cdot 4^{-1} = 16 \equiv 1 \mod 15 $$

$$ 11^{-1} = 11 \rightarrow 11 \cdot 11^{-1} = 121 \equiv 1 \mod 15 $$

$$ 14^{-1} = 14 \rightarrow 14 \cdot 14^{-1} = 196 \equiv 1 \mod 15 $$

Quindi, gli inversi moltiplicativi delle basi sono 1, 4, 11, 14

$$ 1 \cdot 4^{-1} = 1 \cdot 4 \equiv 1 \mod 15  $$

$$ 1 \cdot 11^{-1} = 1 \cdot 11 \equiv 1 \mod 15  $$

$$ 1 \cdot 14^{-1} = 1 \cdot 14 \equiv 1 \mod 15  $$

$$ 4 \cdot 11^{-1} = 4 \cdot 11 = 44 \equiv 14 \mod 15  $$

$$ 4 \cdot 14^{-1} = 4 \cdot 14 = 56 \equiv 11 \mod 15  $$

$$ 11 \cdot 14^{-1} = 11 \cdot 14 = 154 \equiv 14 \mod 15  $$

Il prodotto di una base per l'inverso dell'altra genera dei numeri pseudoprimi con 15.

La dimostrazione

Considero un numero composto \( n \) dispari.

Per ipotesi \( n \) è pseudoprimo nelle basi \(b_1\) e \(b_2\), cioè:

$$ b_1^{n-1} \equiv 1 \pmod{n} $$

$$ b_2^{n-1} \equiv 1 \pmod{n} $$

Poiché \( n \) è pseudo primo con \(b_1 \) e \( b_2 \) deduco che questi siano anche relativamente primi con \( n \)

$$  \gcd(b_1, n) = 1 $$

$$ \gcd(b_2, n) = 1 $$

Devo dimostrare che \( n \) è pseudoprimo anche nelle basi \( b_1 b_2 \) e \( b_1 b_2^{-1} \), dove \( b_2^{-1} \) è l'inverso moltiplicativo di \(b_2\) modulo \(n\).

1] Il caso della base b₁b₂

So già che \( n \) è pseudoprimo nelle basi \( b_1 \) e \( b_2 \), quindi

$$ b_1^{n-1} \equiv 1 \pmod{n} $$

$$ b_2^{n-1} \equiv 1 \pmod{n} $$

Ora voglio dimostrare che \( n \) è pseudoprimo nella base \(b_1 b_2\) cioé che

$$ (b_1 b_2)^{n-1} \equiv 1 \pmod{n} $$

Sfrutto la proprietà delle potenze:

$$ (b_1 b_2)^{n-1} = b_1^{n-1} \cdot b_2^{n-1} $$

Poiché so già che \(b_1^{n-1} \equiv 1 \pmod{n}\) e \(b_2^{n-1} \equiv 1 \pmod{n}\), sostituendo e moltiplicando ottengo 1.

$$ (b_1 b_2)^{n-1} = (1) \cdot (1) \equiv 1 \pmod{n} $$

Quindi \( n \) è pseudoprimo anche nella base \(b_1 b_2\).

2] Il caso della base b₁b₂^-1

Ora considero la base \(b_1 b_2^{-1}\). Devo verificare che:

$$ (b_1 b_2^{-1})^{n-1} \equiv 1 \pmod{n} $$

Applico la proprietà delle potenze

$$ (b_1 b_2^{-1})^{n-1} = b_1^{n-1} \cdot (b_2^{-1})^{n-1} $$

Per ipotesi iniziale \(b_1^{n-1} \equiv 1 \pmod{n}\) perché \( b_1 \) è pseudoprimo con $ n $

$$ (b_1 b_2^{-1})^{n-1} = 1 \cdot (b_2^{-1})^{n-1}  \pmod{n} $$

Ora \((b_2^{-1})^{n-1}= (b_2^{n-1})^{-1}\) per la proprietà delle potenze.

$$ (b_1 b_2^{-1})^{n-1} = 1 \cdot (b_2^{n-1})^{-1}  \pmod{n} $$

Sapendo che \(b_2^{n-1} \equiv 1 \pmod{n}\) per l'ipotesi iniziale.

$$ (b_1 b_2^{-1})^{n-1}  \equiv 1 \cdot (1)^{-1}  \pmod{n} $$

$$ (b_1 b_2^{-1})^{n-1}  \equiv 1 \cdot 1  \pmod{n} $$

$$ (b_1 b_2^{-1})^{n-1}  \equiv 1 \pmod{n} $$

Quindi \( n \) è pseudoprimo nella base \(b_1 b_2^{-1}\).

Questo dimostra che, se \(n\) è pseudoprimo nelle basi \(b_1\) e \(b_2\), allora lo è anche nelle basi \(b_1 b_2\) e \(b_1 b_2^{-1}\).

Nota. Questo risultato è interessante perché mostra che gli pseudoprimi hanno una certa struttura moltiplicativa, che può essere utile per generare nuovi pseudoprimi a partire da quelli noti.

E così via.