Wieferich primes

- Yathirajsharma M. V.

Introduction to the article: In this article, the author describes how he got to know about Wieferich primes.

---

'Are there infinitely many Wieferich Pirmes?' - An unsolved problem

I follow questions and answers on Mathematics Stack Exchange. Sometimes, I try to answer questions which lie within the realm of my knowledge. Of course, one earns reputation if people like and accept the answers (I have very less reputation for that matter). But that is not the main intention why many people are there. Many, extremely good questions, neatly constructed, indicating all the efforts put so far for solving it, do not let one sit quietly. Sometimes it is a collective effort solving a problem.

Recently I came across the following problem:

Problem. What is the least value of \(n\) such that \(n\) divides \(2^n-2\) but not \(3^n-3\)?

When I saw the question, I knew this has something to do with the pseudo Fermat prime to the base \(2\) but not to the base \(3\). One can clearly reject primes in place of \(n\) as Fermat's little theorem allows \(n\) to divide \(a^n-a\) for any \(a\) whenever \(n\) is a prime. I searched for pseudo Fermat primes to the base \(2\). The first such prime is \(341\). It was not that I had no idea about \(341\). But I hadn't seriously thought about it before this.

A Composite number \(a\) is said to be pseudo Fermat prime to the base \(b\), if
\(b^{a-1} \equiv 1 \pmod a\).

Very recently, I had investigated Carmichael numbers to some extent in [1]. Carmichael numbers are counter examples to the converse of Fermat's little theorem. To be precise, these are the composite numbers \(n\) such that for every \(a\) relatively prime to \(n\), we have that \(n\) divides \(a^{n-1}-1\). The very first such number is \(561\). Further, if a number \(n\) is Carmichael, then it satisfies certain properties. Two among them are:

• \(n\) is square free. That is for any prime \(p\), \(p^2\) does not divide \(n\).
• \(n\) is always odd.

One can easily prove these properties of Carmichael numbers. Now, my mind was running in the same direction. The way I could arrive at \(561\) in a constructive manner without any 'brute-force' in [1] was now forcing me to do the same for \(341\). I was now thinking, why \(n=341\) is the first such number such that \(2^n-2\) is divisible by \(341\). Of course, the answer is very simple that it is because there is no other number less than \(341\) which has that property. But my question didn't have only that sense. I wanted to know really what property of numbers is not allowing the numbers less than \(341\) not to satisfy that required condition.

I ran a maxima program to check if I can venture into proving that if \(n\) is a pseudo Fermat prime to the base \(2\), then \(n\) must be square free, that is no square of a prime divides \(n\). I checked numbers till \(10^6\) and the observation revealed that I might go ahead. I started my invsetigation. Before explaining the same, let me recall some notations and facts. Firstly, the language of congruence is familiar to us. For any integers \(a\) and \(b\) and for any positive integer \(n\), we say,

\(a \equiv b \pmod n\), read as \(a\) is congruent to \(b\) modulo \(n\),

if \(n\) divides \(a-b\). Otherwise, we say \(a\) is incongruent to \(b\) modulo \(n\) denoted by

\(a\not\equiv b \pmod n\).

We know the following standard fact from elementary number theory, which in its essence says, primitive root modulo \(p^2\) exists:

Fact 1 [2, p. 161]: If \(p\) is an odd prime, then there is a positive integer \(a\) less than \(p^2\) which is relatively prime to \(p^2\) such that any other number \(b\) which is relatively prime to \(p^2\) can be expressed as some power of \(a\) modulo \(p^2\). That is, \(b \equiv a^k \pmod{p^2}\) for some positive integer \(k\), whenever \(gcd(b,p^2)=1\). We shall call such an \(a\) to be primitive root modulo \(p^2\).

We know that for any integer \(a\) and for any positive inetegr \(n\), \(a^\phi(n)\equiv 1 \pmod n\), where \(\phi(n)\) is the Euler's totient function. This is the famous Euler's theorem. Now, if \(U_n\) denotes the set of all positive integers less than \(n\) and are relative prime to \(n\), then we define the order of any \(a\in U_n\) to be the smallest postive number \(k\) such that

\(a^k \equiv 1 \pmod n\)

Owing to Fact 1, it is clear that the order of a primitive root modulo \(p^2\) is always \(\phi(p^2)= p(p-1)\), as it must generate all elements relative prime to \(p^2\) which are \(p(p-1)\) in number. We have the following general fact about the order of elements in \(U_n\):

Fact 2 [2, p. 148]: If \(k\) is order of \(a\) in \(U_n\) and that \(a^t \equiv 1 \pmod n\), then \(k|t\).

Now coming to the proof I tried for showing that if \(n\) is a composite number satsifying \(n|2^n-2\), then \(n\) must be square free:

---

My Attempt. Supopse \(n\) satisfies \( n|2^{n}-2\). Also suppose that \(p^2\) divides \(n\) for some prime \(p\). Let \(n=p^km\), where \(k\geq 2\) and that \(gcd(p,m)=1\).It is quite easy to see that \(4\) never divides number of the form \(2^n-2\) for any \(n>1\). Hence, we may assume that \(p\) is odd. Suppose,

\(2^n\equiv 2 \pmod n\). This implies \(2^{p^km}\equiv 2\pmod{p^2}\).

Suppose \(a\) is a primitive root modulo \(p^2\). Since \(p\) is an odd pirme, \(p\) and \(2\) are relatively prime, from Fact 1, we must have an integer \(s\) such that \(2= a^s\). Using this in the above, we find that

\(a^{s(p^km-1)}\equiv 1 \pmod{p^2}\).

From Fact 2, it now follows that order of \(p^2\) must divide \(s(p^km-1)\). That is \(p(p-1)\) must divide \(s(p^km-1)\). Quite clearly, \(p\) must divide \(s(p^km-1)\). As \(gcd(p^km-1, p)=1\), this implies that \(p\) must divide \(s\). Let \(s=pr\). Now

\(a^s \equiv 2 \pmod{p^2} \implies a^{pr} \equiv 2\pmod{p^2} \implies a^{p(p-1)r} \equiv 2^{p-1} \pmod{p^2}\).

However, \(a^{p(p-1)r} \equiv 1 \pmod{p^2}\). Hence, we have

\(2^{p-1} \equiv 1 \pmod{p^2}\).

---

I stopped my proof here. This was a beautiful stop! I couldn't continue my journey further. I knew that \(2^{p-1}\equiv 1 \pmod{p}\), for any odd prime \(p\). It was now enough for me to show that for no odd prime \(p\), \(2^{p-1}\equiv 1 \pmod{p^2}\). This was appearing to be quite easy for me. But when all my thoughts failed, I ran another maxima program to verify whether any such primes existed. Surprisingly, maxima answered that \(1093\) and \(3511\) possess the property that

\(2^{1092} \equiv 1\pmod{1093^2}\) and \(2^{3510}\equiv 1 \pmod{3511^2}\).

Very strangely, till \(10^6\) no other primes \(p\) possess this property. I was surprised to know that till today no primes \(p\) other than \(1093\) and \(3511\) satisfy

\(2^{p-1} \equiv 1 \pmod{p^2}\).

These primes, called by the name, Wieferich primes were first described by Arthur Wieferich in one of his works related to Fermat's Last Theorem in 1909. I then went through the wiki article on Wieferich primes - Wiki-Article-Wieferich-Primes to know about the status of the same.

It was quite interesting to even know about Arthur Wieferich, who, after his graduation became a school teacher abandoning all his researches. As said in wiki-article, one may extend the study to other bases, i.e., given any prime \(p\), one may look for primes \(q\) other than \(p\) such that

\(p^{q-1} \equiv 1\pmod{q^2}\).

As guessed, one is led to the conjecture that, for each such \(p\) (base), one finds only finitely many \(q\) satisfying the above congruence. The following table gives list of few Wieferich primes less than \(10^5\) to the prime bases less than \(100\). This is not an exhaustive list. The numbers here are within the limit of maxima software.

Prime \(p\)	\(q\) such that \(p^{q-1}\equiv 1 \pmod{q^2}\)
\(2\)	\(1093, 3511\)
\(3\)	\(11\)
\(5\)	\(2,20771,40487\)
\(7\)	\(5\)
\(11\)	\(71\)
\(13\)	\(2, 863\)
\(13\)	\(2, 863\)
\(17\)	\(2,3,46021,48947\)
\(19\)	\(3, 7, 13, 43, 137\)
\(23\)	\(13\)
\(29\)	\(2\)
\(31\)	\(7, 79, 6451\)
\(37\)	\(2,3,77867\)
\(41\)	\(2, 29\)
\(43\)	\(5, 103\)
\(47\)	No Prime
\(53\)	\(2,3,47,59,97\)
\(59\)	\(2777\)
\(61\)	\(2\)
\(67\)	\(7,47\)
\(71\)	\(3,47,331\)
\(73\)	\(2,3\)
\(79\)	\(7,263,3037\)
\(83\)	\(4871,13691\)
\(89\)	\(2,3,13\)
\(97\)	\(2,7\)

In the same wiki article, it has been noted that few people believe that there are infinitely many Wieferich primes to the base \(2\) for some good reasons. And hence, one may, as nobody knows, conjecture that there are infinitely many Wieferich primes to any base \(b\). Oh! I had been deviated for a while from my original task - checking if \(n\) is square free whenever \(n\) divides \(2^n-2\). That problem is also solved as

\(2^{1092^2}\equiv 2^{1092} \equiv 2 \pmod{1092^2}\)

Evidently \(n\) need not be square free.

References.

[1] A revisit to Carmichael numbers and a note on Carmichael triplets, Yathirajsharma M. V.

[2] Elementary Number Theory, David M. Burton

---

Yathirajsharma M. V. currently works as an Assistant Professor of Mathematics at Sarada Vilas College.

---

If you find any mistakes or errors, please send the same to dep.math.svc@gmail.com