# Lemma R of section 3.2 (The Art of Computer Programming)

In "The Art of Computer Programming" by Donald Knuth, the proof of lemma R starts with the assumption that $$\lambda = p^e$$ which means:
$$\left({a^{p^e}-1\over a-1}\right)\equiv 0\pmod{p^e}$$ The above condition leads to: $$a\equiv1\pmod{p^e}\quad(1)$$ Knuth also considers the case when $$p=2$$ and $$a\equiv3\;(\operatorname{mod} 4)$$.We then have: $$(a^{2^{e-1}}-1)/(a-1)\equiv 0\pmod{2^e}$$ Or: $$a^{2^{e-1}}\equiv a^{2^e}\pmod{2^e}$$ He then writes:

These arguments show that it is necessary in general to have $$a=1+qp^f$$,where $$p^f>2$$ and $$q$$ is not a multiple of $$p$$, whenever $$\lambda=p^e$$

I have two questions here:

1. Why would we need to consider the case when $$p=2$$ and $$a\equiv3\pmod4$$?
2. What proves $$a=qp^f+1$$?

In "The Art of Computer Programming" by Donald Knuth, the proof of lemma R starts with the assumption that $$\lambda = p^e$$ which means:
$$\left({a^{p^e}-1\over a-1}\right)\equiv 0\pmod{p^e}$$ The above condition leads to: $$a\equiv1\pmod{p^e}\tag 1$$
If you read more carefully, that condition does not lead to formula (1). It only leads to $$a\equiv1\pmod{p}\tag{2 }$$ In the case of $$p=2$$, the above condition is $$a\equiv1\pmod{2}\tag{3 }$$ which falls short of $$a\equiv1\pmod{4}\tag{4 }$$ That is why Knuth has to exclude the case of $$a\equiv3\pmod{4}$$ before asserting the formula (4).
What proves $$a=qp^f+1$$, where $$p^f > 2$$?
Formula (2) implies $$a=qp^1+1$$ for all $$p>2$$, where $$p^1=p>2$$ in. Formula (4) implies $$a=q4+1$$ when $$p = 2$$, where $$4=2^2>2$$.