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.