2
$\begingroup$

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$?
$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.