Multiplicative Property of Bases in Euler Pseudoprimes

If $ n > 1 $ is an odd composite number and an Euler pseudoprime in bases $ b_1 $ and $ b_2 $, meaning that $ \text{GCD}(b_1, n) = \text{GCD}(b_2, n) = 1 $ for two coprime bases in the range $ 1 < b < n $, then $ n $ is also an Euler pseudoprime for the product of the two bases, $ b_1 b_2 $, and for $ b_1 b_2^{-1} $, where $ b_2^{-1} $ is the modular inverse of $ b_2 $ modulo $ n $.

In other words, Euler pseudoprimality is preserved when bases are multiplied or when one base is replaced with its modular inverse.

This reveals an underlying structure in Euler pseudoprimes that makes them "stable" under specific base transformations.

Why does this matter? This property allows me to identify additional Euler pseudoprimes from just two known bases within the range $ 1<b<n $. If I already know two bases that confirm $ n $ as an Euler pseudoprime, I can leverage them to discover more valid bases. This is particularly useful in primality testing: instead of checking each base individually, I can start with a couple and then use multiplication to generate others effortlessly.

A Practical Example

Let’s take an odd modulus $ n = 21 $ and the bases $ b_1 = 8 $ and $ b_2 = 13 $.

Both 8 and 13 are coprime with 21.

$$ \text{GCD}(8, 21) = 1 $$

$$ \text{GCD}(13, 21) = 1 $$

So, these bases are valid.

1] Checking Euler Pseudoprimality for the Given Bases

Now, let’s verify that $ n = 21 $ is an Euler pseudoprime in bases $ b_1 = 8 $ and $ b_2 = 13 $.

A number $ n $ is an Euler pseudoprime in base $ b $ if:

\[ b^{(n-1)/2} \equiv \pm 1 \pmod{n} \]

For $ b_1 = 8 $:

\[ 8^{(21-1)/2} \pmod{21} \]

\[ 8^{10} \pmod{21} \]

Since $ 8^2 = 64 \equiv 1 \pmod{21} $, we get:

$$ 8^{10} = (8^2)^5 \equiv 1^5 = 1 \pmod{21} $$

So, $ n = 21 $ is an Euler pseudoprime in base $ b_1 = 8 $.

For $ b_2 = 13 $:

\[ 13^{(21-1)/2} \pmod{21} \]

\[ 13^{10} \pmod{21} \]

Since $ 13^2 = 169 \equiv 1 \pmod{21} $, we conclude:

$$ 13^{10} = (13^2)^5 \equiv 1^5 = 1 \pmod{21} $$

Thus, $ n = 21 $ is also an Euler pseudoprime in base $ b_2 = 13 $.

2] Checking Pseudoprimality for the Product of the Bases

Next, we check whether $ n = 21 $ remains an Euler pseudoprime for $ b_1 b_2 $ and $ b_1 b_2^{-1} $.

First, we compute the product of the bases:

\[ b_1 b_2 = 8 \cdot 13 = 104 \]

Since $ 104 \equiv 20 \mod 21 $, we check:

\[ 20^{10} \pmod{21} \]

To determine whether $ n = 21 $ is an Euler pseudoprime in base $ 20 $:

Since $ 20^2 = 400 \equiv 1 \pmod{21} $, we have:

\[ 20^{10} = (20^2)^5 \equiv 1^5 = 1 \pmod{21} \]

This confirms that $ n = 21 $ is an Euler pseudoprime in base $ b_1 b_2 = 20 $.

Finally, let’s verify whether 21 is still an Euler pseudoprime in the base $ b_1 b_2^{-1} $:

\[ b_1 b_2^{-1} \pmod{21} \]

\[ 8 \cdot b_2^{-1} \pmod{21} \]

We need the modular inverse of $ b_2 = 13 $ modulo $ n = 21 $, meaning we find $ b_2^{-1} $ such that:

\[ 13 \cdot b_2^{-1} \equiv 1 \pmod{21} \]

Using the extended Euclidean algorithm, we determine that $ b_2^{-1} \equiv 13 \pmod{21} $.

\[ 8 \cdot 13 \pmod{21} \]

\[ 104 \equiv 20 \pmod{21} \]

Since the modular inverse of $ b_2 $ coincides with $ b_2 $ itself, we have:

\[ b_1 b_2 = b_1 b_2^{-1} = 8 \cdot 13 = 104 \]

Since we already confirmed that $ n = 21 $ is an Euler pseudoprime in base $ 20 $, there’s no need to repeat the calculations.

\[ 20 \equiv 1 \pmod{21} \]

This completes the proof.

Final Check. For completeness, let’s examine all bases coprime with $ n=21 $ from 1 to 20 and identify which make 21 an Euler pseudoprime.

Base	Calculation	Euler Pseudoprimes
1	$$ 1^{10} \equiv 1 \mod 21 $$	✅ yes
2	$$ 2^{10} \not\equiv 1 \mod 21 $$	❌ no
4	$$ 4^{10} \not\equiv 1 \mod 21 $$	❌ no
5	$$ 5^{10} \not\equiv 1 \mod 21 $$	❌ no
8	$$ 8^{10} \equiv 1 \mod 21 $$	✅ yes
10	$$ 10^{10} \not\equiv 1 \mod 21 $$	❌ no
11	$$ 11^{10} \not\equiv 1 \mod 21 $$	❌ no
13	$$ 13^{10} \equiv 1 \mod 21 $$	✅ yes
16	$$ 16^{10} \not\equiv 1 \mod 21 $$	❌ no
17	$$ 17^{10} \not\equiv 1 \mod 21 $$	❌ no
19	$$ 19^{10} \not\equiv 1 \mod 21 $$	❌ no
20	$$ 20^{10} \equiv 1 \mod 21 $$	✅ yes

Indeed, 21 is an Euler pseudoprime in bases 1, 8, 13, and 20. This confirms our result.

And so on.