Congruences between Fermat quotients

Question

This a repost of a question I asked at Stack Exchange:

https://math.stackexchange.com/questions/35264/congruences-for-fermat-quotients

I didn't get a complete answer to my question, so I'm trying again here.

If $p$ is a prime number and $a$ is relatively prime to $p$, then by Fermat's Little Theorem, the Fermat quotient $q_p(a) = (a^{p-1}-1)/p$ is an integer. To summarize that other post, I stumbled across some congruences relating Fermat quotients and wonder 1) if these and/or similar congruences are known, and 2)where I can find other proofs than my own, either simple enough to post here or written up somewhere.

Here are some examples:

If $p = 2^a-1$ is a Mersenne prime, so $a$ is prime, then $q_p(2) \equiv 2q_a(2) \pmod{p}$.

If $p = 2^n-3$ is prime for some $n$, then $3nq_p(2) + 1 \equiv 3q_p(3) \pmod{p}$

If $p = 3^n-4$ is prime for some $n$, then $4nq_p(3) + 1 \equiv 8 q_p(2) \pmod{p}$

I have proved a few others of this nature and seem to have a way to generate more if I wish.

Edit: These and other similar congruences follow from an elementary argument of Edmund Landau. See my answer to my own question belowl.

Answer 1

Let just try a look at your first result:

Corollary 1 in Johnson, Wells paper above says:

Let $\epsilon = 1,-1$ and let $p=2^r+ \epsilon$ be a prime number. Then

$$ q_p(2) \equiv \frac{\epsilon}{r} \pmod{p} $$

Your result for a Mersenne prime (taking $\epsilon =-1$ above) follows from this:

Observe that (trivially) $2^r \equiv 1 \pmod{p}$. Thus $2^r-2 \equiv -1 \pmod{p}$

In other words:

$$ 2q_r(2) \equiv (2^r -2) \frac{1}{r} \equiv (-1) \cdot \frac{1}{r} \equiv \frac{\epsilon}{r} \equiv q_p(2) \pmod{p} $$

Thus $$ q_p(2) \equiv 2q_r(2) \pmod{p}. $$

Answer 2

After further thought, I realized that most of these congruences are all immediate consequences of the well-known property of Fermat quotients

$$ q_p (a^n) \equiv n q_p (a) \pmod{p} $$

along with the following property: if $p$ is an odd prime and $r$ is an integer and we write $r p = a \pm b$ with $(p,ab)=1$, then

$$ a q_p (b) \pm b q_p(a) \equiv r \pmod{p} $$

Together, these show that if $rp = a^m \pm b^n$, then

$$ a^m nq_p (b) \pm b^n m q_p (a) \equiv r \pmod{p} $$

What shocks me is that these latter congruences have a short completely elementary proof but are not mentioned in a lot of the literature on Fermat quotients. I'd add them to the basic properties of Fermat quotients on Wikipedia, except that I doubt one post on a forum constitutes a reliable source.

To prove the second congruence above, note that

$$ b q_p(a) p = b (a^{p-1} - 1) = b \left( (rp \mp b)^{p-1} - 1 \right) \equiv b \left( \mp b^{p-2} r (p-1) +q_p(b) \right) p \pmod{p^2} $$

and thus

$$ b q_p(a) \equiv \pm b^{p-1} r + b q_p(b) \equiv \pm r + b q_p(b) \pmod{p} $$

Since $a \equiv \mp b \pmod{p}$ it follows that

$$ \pm b q_p(a) \equiv r - a q_p(b) \pmod{p}$$

from which the second congruence above follows.

Edit: I finally found a reference! I knew this simple of a result could not be new! The earliest I can find is from a journal called "L'Intermediaire des Mathematiciens", of which I had not previously heard. It seems fascinatingly to be a publication where people could pose short questions hoping that others would answer --- perhaps like a paper version of MO! Does anyone know the history of this journal? Was its function indeed like an early version of MO?

On p.121, volume 20, published 1913, one E. Dubouis poses the question (numbered 3764): How does one prove the theorem of Mirimanoff (C.R. 24 January 1910): `If p is a prime number of the form $2^a 3^b \pm 1$ or of the form $\pm 2^a \pm 3^b$, then at least one of the numbers $2^{p-1} - 1$ and $3^{p-1} -1$ is not divisible by $p^2$?' "

Later in that same volume, p.206, one finds an answer by Endmund Landau: "One can easily prove the more general fact that the following three lines lead to a contradiction:

$$ mp = x+y $$ $$ p \text{ odd } > 1 \text{ and not dividing } m $$ $$ x^{p-1} \equiv y^{p-1} \equiv 1 \pmod{p^2} $$

(These congruences are satisfied for $x=2^a 3^b$, $y = \pm 1$ and for $x = \pm 2^a$, $y = \pm 3^b$, if $2^{p-1} \equiv 3^{p-1} \equiv 1 \pmod{p^2}$; taking $m=1$ and $p$ prime, we recover the question posed by M. Dubouis.) We have:

$$ 1 \equiv x^{p-1} \equiv (mp-y)^{p-1} \equiv -(p-1) mpy^{p-2}+y^{p-1} \equiv -(p-1) mpy^{p-2} + 1 \pmod{p^2}$$

and $p$ divides $(p-1) m y^{p-2}$, hence $m$, contrary to hypothesis."

So although E. Landau doesn't explicitly state the second congruence above, the proof I gave is almost the same as Landau's.

Answer 3

Check the following two papers. Try to get the actual papers. The first one by Emma Lehmer is a classic paper that has only a german review (not included) in ZBL but has lots of nice properties of the fermat quotient inside.

JFM 64.0095.04 Lehmer, E.

On congruences involving Bernoulli numbers and the quotients of Fermat and Wilson. (English)

Ann. Math., Princeton, (2) 39, 350-360 (1938). Reviewer: Petersen, H. (Frörup über Flensburg)

and:

MR0450193 (56 ,8489) Johnson, Wells On the nonvanishing of Fermat quotients $({\rm mod}$ $p)$. J. Reine Angew. Math. 292 (1977), 196–200. 10B15 (10A30)

The author derives various conditions on $p$ and $a$ that ensure that $q_a\not\equiv 0\ (\text{mod}\,p)$, where $q_a$ is the Fermat quotient modulo $p$, i.e. $q_a=(a^{p-1}-1)/p$. The results imply the validity of the Fermat conjecture in the first case for prime exponents, $p$, which linearly divide the sums $a^{(s-1)k}\pm a^{(s-2)k}\pm\cdots\pm a^k+1$, where $p\nmid s$ and $2\leq a\leq 31$. Noting that the two primes $p$ known, 1093 and 3511, for which $q_2\equiv 0\ (\text{mod}\,p)$, exhibit a certain cyclicity in their binary expansions, the author deduces that primes $p$ that have a similar property in their $a$-adic expansion satisfy $q_a\not\equiv 0\ (\text{mod}\,p)$. Reviewed by Graham Lord

Answer 4

In the cited paper by Wells Johnson, where the Theorem sets $a^r = \pm 1 + tp$, instead set $a^r = a + 1 + p$, but maintain the underlying logic of the proof. Then this adaptation of his result gives $q_{a} = \frac{1}{r}(q_{a+1} - \frac{1}{a+1})$, which in your notation, assuming $p = a^n - a - 1$, is

$(a+1)nq_{p}(a) + 1 \equiv (a+1)q_{p}(a+1)$ (mod $p$),

the desired expression.

Your result, a consequence of Johnson's work that seems to have been previously overlooked, is interesting because it clearly reveals that for $p$ of the required forms, $q_{p}(2)$ and $q_{p}(3)$ cannot vanish simultaneously (a question addressed in the cited paper by Emma Lehmer).

In this vein, if instead of $a^r = a + 1 + p$ we take $a^r = a - 1 + p$, then $q_{a} = \frac{1}{r}(q_{a-1} - \frac{1}{a-1})$, or in your notation, assuming $p = a^n - a + 1$,

$(a-1)nq_{p}(a) + 1 \equiv (a-1)q_{p}(a-1)$ (mod $p$).

Thus, taking $a = 3$, if $p$ can be expressed in the form $3^n - 2$, we have

$2nq_{p}(3) + 1 \equiv 2q_{p}(2)$ (mod $p$).

Taking $a = 4$, if $p$ can be expressed in the form $4^n - 3$, we have

$3nq_{p}(4) + 1 \equiv 3q_{p}(3) \rightarrow 6nq_{p}(2) + 1 \equiv 3q_{p}(3)$ (mod $p$).

Taking $a = 9$, if $p$ can be expressed in the form $9^n - 8$, we have

$8nq_{p}(9) + 1 \equiv 8q_{p}(8) \rightarrow 16nq_{p}(3) + 1 \equiv 24q_{p}(2)$ (mod $p$).

The cases which relate $q_{p}(2)$ to $q_{p}(3)$ are merely some of the more interesting implications of the reformulation of Johnson's theorem suggested by your posting. Finally, if $p$ has the form $a^n -k$, where neither $a$ nor $k$ is divisible by $p$ nor greater than 89, a similar argument establishes the first case of Fermat's Last Theorem for $p$, since the failure thereof would require the vanishing of $q_{p}(a)$ for every $a \le 89$, as proved by Granville.