Multiplicative Property of Pseudoprimes

Given an odd composite number $n > 1$, if $n$ is a pseudoprime in bases $b_1$ and $b_2$, then it is also a pseudoprime in the product of the bases $b_1b_2$ as well as in the product of one base with the modular inverse of the other: $b_1 b_2^{-1}$ and $b_1^{-1} b_2$.

This result highlights a fundamental property of pseudoprimes, closely tied to Fermat pseudoprimes.

It reveals an inherent multiplicative structure among pseudoprimes for certain bases.

Why is this useful?

This property provides a systematic way to construct new pseudoprimes from known ones.

A Practical Example

Let's consider an odd composite number greater than 1—say, 15.

$$n=15$$

Since 15 is composite, we can write it as $15 = 3 \cdot 5$.

Now, let's identify bases $b$ for which this number is a pseudoprime.

A number is a pseudoprime with respect to $n=15$ if it is relatively prime to $n$ and satisfies $b^{n-1} \equiv 1 \mod n$.

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

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

First, we list the integers relatively prime to 15:

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

Next, we check which of these satisfy the pseudoprime condition:

$$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$$

Thus, the pseudoprimes with respect to 15 are $1^{14}, 4^{14}, 11^{14}, 14^{14}$, corresponding to the bases 1, 4, 11, and 14.

A] The Product of the Bases

Now, let's check whether multiplying these bases together still results in a pseudoprime modulo 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$$

We see that the products 1, 11, and 14 are also pseudoprimes modulo 15.

B] The Product of One Base with the Inverse of Another

Next, we determine whether multiplying a base by the modular inverse of another still results in a pseudoprime modulo 15.

First, we find the modular inverses of 1, 4, 11, and 14—numbers satisfying $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$$

Thus, the modular inverses of the bases are 1, 4, 11, and 14. Now, we verify the products:

$$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$$

As expected, these products also yield pseudoprimes modulo 15.

Proof

Let $n$ be an odd composite number.

By assumption, $n$ is a pseudoprime in bases $b_1$ and $b_2$, meaning:

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

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

Since $n$ is pseudoprime for both bases, it follows that $b_1$ and $b_2$ are relatively prime to $n$:

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

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

Now, we need to show that $n$ is also a pseudoprime in bases $b_1 b_2$ and $b_1 b_2^{-1}$, where $b_2^{-1}$ is the modular inverse of $b_2$ modulo $n$.

1] The Case of $b_1b_2$

Using exponentiation rules:

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

Since both terms are congruent to 1, their product is also 1:

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

Thus, $n$ is pseudoprime in base $b_1 b_2$.

2] The Case of $b_1b_2^{-1}$

Applying exponentiation properties:

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

This confirms that $n$ is also a pseudoprime in base $b_1 b_2^{-1}$.

Note: This result demonstrates a multiplicative structure in pseudoprimes, offering a method to generate new ones from existing examples.