Could Fermat's Little Theorem be expanded to include some semiprimes for p?

96 Views Asked by At

Fermat's Little Theorem states that a^p%p=a. For example, if a=2, then 2^p%p=2 if p is any prime. That's all the theorem says. However, I tried plugging in 3p instead of p, and I got an interesting result. For all p that I tested (all primes up to 100), the modded result is 8 (or 2^3). I also tried 5 and 7, but the results didn't seem to have a clear pattern. Is it possible that some semiprimes combinations could be found through Fermat's Little Theorem?

1

There are 1 best solutions below

2
On BEST ANSWER

Interesting observation.

The point here is that $2\equiv -1\pmod 3$.

It follows from that that, for odd $p$, $$2^{3p}\equiv -1\pmod 3$$

Now, of course, $$2^{3p}\equiv 8 \pmod p$$ by Little Fermat.

Noting that $8\equiv -1\pmod 3$, we see that the unique solution to this pair of congruences is $$2^{3p}\equiv 8\pmod {3p}$$ at least for $p>3$.

As you can see, however, this all depends on a number of numerical accidents.