Saturday, 24 January 2026

Exercise (4.4).7

Determine the first error in the following derivation and give reasons for your answer:

Step A: A prime factor $q$ of $2^{193} − 1$ is of the form

$$q= (2 × 193 × k) + 1 = 386k + 1$$

Step B: Substituting $k= 1$ into this $q= 386k + 1$ gives $q= 387$ which is composite.

Step C: Substituting $k= 2$ into this $q= 386k + 1$ gives $q= 773$ which is prime.

Step D: Therefore, 773 is a prime factor of $2^{193} − 1$.


Step A is correct by Proposition (4.23) since 193 is prime.

Step B is correct.

Step C is correct.

Step D is incorrect. By Proposition (4.24) any prime factor of $2^{192}-1$ must be congruent to $\pm 1 \pmod 8$. However $773 \equiv 5 \pmod 8$, and so is ruled out as a prime factor of $2^{193}-1$.