Posted by Jason Polak on 04. February 2016 · Write a comment · Categories: math

Fermat’s little theorem says that $p | a^{p-1} – 1$ whenever $p$ is a prime and $a$ is any integer not divisible by $p$. For example, $13 | 2^{12} – 1$. Fermat’s little theorem doesn’t tell you how many times $p$ divides into $a^{p-1}-1$, however. In fact, $p^k | a^{p-1}-1$ for $k > 1$ is pretty rare. For $a = 2$ these are called Wieferich primes and are quite rare. In fact, the only $p < 10^6$ for which $p^2 | 2^{p-1} - 1$ are 1093 and 3511 -- and I believe even more effective searches have failed to turn up other primes. For $a = 3$, there is only one prime under two hundred thousand that works: 11. Indeed, 3^11 - 1 = 2^3 * 11^2* 61. For 31 there are only two primes under a hundred thousand: 79 and 6451.

Given a positive natural number $n$ does there exist an integer $a$ and a prime $p\nmid a$ such that $p^n | a^(p-1) – 1$? Of course. You can always use $p=2$ and $a = 2^n + 1$. That’s kind of boring, so what if we require that $p$ be odd? Yes, you can still do it. Let’s look at an example:

193^(5-1) – 1 = 2^8 * 3 * 5^3 * 97 * 149

so for $n = 3$ our conjecture is true. What about $n=4$? Yes!

163^(3-1) = 2^3 * 3^4 * 41

How high can we go to test our conjecture? Here is a quick sampling:

n Example
5 487^(3-1) – 1 = 2^4 * 3^5 * 61
6 1459^(3-1) – 1 = 2^3 * 3^6 * 5 * 73
7 4373^(3-1) -1 = 2^3 * 3^7 * 1093
8 13121^(3-1) = 2^7 * 3^8 * 5 * 41
9 984149^(3-1) = 2^3 * 3^9 * 5^2 * 11 * 22367
10 590489^(3-1) = 2^4 * 3^10 * 5 * 31 * 2381

Notice that all the primes now are $p=3$. Maybe $p=2,3$ are special cases. Not so! Take a look:

n Example
4 443^(5-1)-1 = 2^4 * 3 * 5^4 * 13 * 17 * 37 * 157
5 32261^(7-1) = 2^3 * 3^2 * 5 * 7^5 * 19 * 283 * 1613 * 20641 * 1040804383

Of course, the bigger the prime you want to use for the exponent, the bigger the example. After a while, they get pretty unwieldy:

2120879^10 -1 = 2^5 * 3 * 5^2 * 11^6 * 41 * 373 * 2843 * 8681 * 8837 * 23371 * 100361 *
6417762403561 * 8626239208485611

Here’s another:

38277341^(17-1)-1 = 2^6 * 3^2 * 5 * 17^7 * 53 * 73 * 1777 * 4649 * 40123 * 247601 * 1913867 * 24739541 * 29611601 * 18910526738927041 * 3162675560928260110522553 * 674867005418656431349286401

Obviously, finding a base that works with a prime is much easier than finding a prime for a fixed base.

Leave a Reply

Your email address will not be published. Required fields are marked *