0

Find all bases $b$ such that $15$ and $21$ are pseudoprimes,i.e. $b^{14} \equiv 1 (mod 14)$ and $b^{20} \equiv 1 (mod 20)$

Can anyone help me?

Muniain
  • 1,453
  • 2
    Do you mean to say, "Find all pseudoprimes in base $15$ and $21$" or "Find all bases $b$ such that $15$ and $21$ are pseudoprimes?" (It's probably the latter, because by the usual definition of pseudoprimes, there are infinitely many pseudoprimes in any base.) – George V. Williams Apr 06 '13 at 13:38
  • What definition of pseudoprime are you using? – Math Gems Apr 06 '13 at 14:22
  • At first I thought $15$ and $21$ had to be interpreted as represented in base $b$ s-/ – Bart Michels Jan 13 '17 at 15:37

2 Answers2

1

Let's solve this for $n = 15$. The proof with $n = 21$ is analogous.

We need to find every $b$ that satisfies $$ b^{14} \equiv 1 \mod 15$$

We can choose $1 \le b \le 14$ and $(b, 15) = 1$, thus we need to check $1, 2, 4, 7, 8, 11, 13, 14$ as potential bases.

All following calculus should be considered $\mod 15$.

  • $1^{14} = 1$, thus 1 works.
  • $2^{14} = (2^4)^3 \cdot 2^2 \equiv 1 \cdot 4 \equiv 4$, thus 2 does not work.
  • $4^{14} = (4^2)^7 \equiv 1^7 \equiv 1$, thus 4 works.
  • $7^{14} = (7^2)^7 \equiv 4^7 \equiv (4^2)^3 \cdot 4 \equiv 1 \cdot 4 \equiv 4$, thus 7 does not work.

We can observe that, since the exponent 14 is even, $$(-b)^{14} = b^{14}$$ This shows that $-1 \equiv 14$ and $-4 \equiv 11$ are bases to which 15 is pseudoprime. Clearly, $-2 \equiv 13$ and $-7 \equiv 8$, are not bases.

Wrapping it up, 15 is pseudoprime to bases 1, 4, 11, 14 (seen mod 15).

lucach
  • 43
1

Hint:

$b^{14}-1 \equiv 0 \mod 15$, GCD $(15,b)=1$. Using this find all such $b$'s (find the general form,as they are infinite)

Inceptio
  • 7,881