\( \definecolor{colordef}{RGB}{249,49,84} \definecolor{colorprop}{RGB}{18,102,241} \)
  1. Let \(p\) be an odd prime number.
    1. Show that there exists a non-zero natural integer \(k\) such that \(2^k \equiv 1 \pmod{p}\).
    2. Let \(k\) be a non-zero natural integer such that \(2^k \equiv 1 \pmod{p}\) and let \(n \in \mathbb{N}\). Show that if \(k\) divides \(n\), then \(2^n \equiv 1 \pmod{p}\).
    3. Let \(b\) be the smallest non-zero integer such that \(2^b \equiv 1 \pmod{p}\). Using Euclidean division of \(n\) by \(b\), show that if \(2^n \equiv 1 \pmod{p}\), then \(b\) divides \(n\).
  2. Let \(q\) be an odd prime number and \(A = 2^q - 1\). Let \(p\) be a prime factor of \(A\).
    1. Justify that \(2^q \equiv 1 \pmod{p}\).
    2. Show that \(p\) is odd.
    3. Let \(b\) be the smallest non-zero integer such that \(2^b \equiv 1 \pmod{p}\). Using question 1, show that \(b\) divides \(q\), and deduce that \(b = q\).
    4. Show that \(q\) divides \((p - 1)\), then show that \(p \equiv 1 \pmod{2q}\).
  3. Let \(A_1 = 2^{17} - 1\). The following is a list of prime numbers less than 400 of the form \(34m + 1\) (where \(m \in \mathbb{N}^*\)): 103, 137, 239, 307. Deduce that \(A_1\) is prime.

Capture an image of your work. AI teacher feedback takes approximately 10 seconds.