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:

**5^3*** 97 * 149

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

**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:

**11^6*** 41 * 373 * 2843 * 8681 * 8837 * 23371 * 100361 *

6417762403561 * 8626239208485611

Here's another:

**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.