Thursday, 29 January 2026

Exercise (4.5).8

(a) Show that $𝜎 (2^n) = 2^{n+1} − 1$.

(b) Show that $𝜎 (p^n) = p^{n+1} − 1$ where $p$ is prime.


(a) The sigma function of a natural number is the sum of all the positive divisors of that number.

The divisors of $2^n$ are $1, 2, 2^2, 2^3, \ldots , 2^n$. And so

$$ \begin{align} \sigma(2^n) & = 1 + 2 + 2^2 + 2^3 \ldots 2^n  \\ \\ & = \frac{1-2^{n+1}}{1-2} \quad \text{geometric sum} \\ \\ & = 2^{n+1} - 1 \end{align}$$

Note: the formula for the sum of a geometric series is here (link).


(b) The assertion is wrong. Consider $p=3$ as a counter-example.

The divisors of $3^n$ are $1, 3, 3^2, 3^3, \ldots , 3^n$. And so

$$ \begin{align} \sigma(3^n) & = 1 + 3 + 3^2 + 3^3 \ldots 3^n  \\ \\ & = \frac{1-3^{n+1}}{1-3} \quad \text{geometric sum} \\ \\ & = \frac{3^{n+1} - 1}{2} \\ \\  & \ne 3^{n+1}-1 \end{align}$$

The correct expression is

$$ \sigma(p^n) = \frac{p^{n+1}-1}{p-1}$$


at

Exercise (4.5).7

Show that the following statement is false:

‘There is one perfect number for any given number of digits.’


The first few perfect numbers are: 6, 28, 496, 8128, 33550336 (src A000396).

This tells us there is no perfect number of five, six or seven digits.


at

Exercise (4.5).6

Show that the following is false:

‘An even number is an abundant number.’


We can show this with a counter-example.

Consider the even number 4. It has two proper factors, 1 and 2$. The sum is 3. which is less than 4, and so 4 is deficient, not abundant.

Another, even simpler example, is the even number 2, whose only proper factor is 1, and so the sum is 1, which is less than 2, leaving 2 as a deficient number.


at

Exercise (4.5).5

Prove that a prime number is a deficient number.


A number $n$ is deficient if the sum of its proper factors is less than $n$.

A prime number $p$ has only two factors, 1 and $p$ itself. It has only one proper factor, 1.


And so any prime is deficient because the sum of its proper factors is always 1, which is less than any prime.


at

Exercise (4.5).4

Determine $\sigma (500)$.


We use the multiplicativity of the sigma function, 

$$ \gcd(a,b)=1  \quad \implies \quad \sigma(a \times b) = \sigma(a) \times \sigma(b) $$

and Proposition (4.35), where $p$ is prime and $k$ is a positive integer,

$$ \sigma(p^k) = \frac{p^{k+1} - 1}{p - 1} $$


Noting $\gcd(2^2, 5^3)=1$, we have

$$\begin{align} \sigma(500) & = \sigma(2^2) \times \sigma(5^3) \\ \\  & =  \frac{2^3-1}{2-1} \times \frac{5^4-1}{5-1} \\ \\ & = 1092 \end{align} $$


at

Exercise (4.5).3

(a) Show that $n$ is an abundant number $\iff 𝜎 (n) > 2n$.

(b) Show that $n$ is a deficient number $\iff 𝜎 (n) < 2n$.

(c) Show that $n$ is a perfect number $\iff 𝜎 (n) = 2n$.

Characterise the numbers in question 2 into perfect, abundant, or deficient numbers.


(a) An abundant number $n$ is one where the sum of its proper factors $p(n)$ is greater than $n$.

Noting the definition $\sigma(n) = p(n) + n$, we have

$$ \text{abundant }n \iff p(n) > n \iff \sigma(n) > n + n  \iff \sigma(n) > 2n $$


(b) A deficient number $n$ is one where the sum of its proper factors $p(n)$ is less than $n$. 

Noting the definition $\sigma(n) = p(n) + n$, we have

$$ \text{deficient }n \iff p(n) < n \iff \sigma(n) < n + n  \iff \sigma(n) < 2n $$


(c) A perfect number $n$ is one where the sum of its proper factors $p(n)$ equals $n$. 

Noting the definition $\sigma(n) = p(n) + n$, we have

$$ \text{perfect }n \iff p(n) = n \iff \sigma(n) = n + n  \iff \sigma(n) = 2n $$


We characterise the numbers from exercise 2 as follows:

  • 15 is a deficient number because $\sigma(15) = 24 < 30$
  • 77 is a deficient number because $\sigma(77)=96 < 154$
  • 171 is a deficient number because $\sigma(171) = 260 < 342$
  • 200 is an abundant number because $\sigma(200)=465 > 400$


at

Exercise (4.5).2

Determine the following:

(a) $\sigma (15)$

(b) $\sigma (77)$

(c) $\sigma (171)$

(d) $\sigma (200)$


The sigma function of a natural number $n$ is the sum of its positive divisors, including 1 and $n$ itself.


(a) $\sigma (15) = 1 + 3 + 5 + 15 = 24$


(b) $\sigma (77) = 1 + 7 + 11 + 77 = 96$


(c) $\sigma (171) = 1 + 3 + 3^2 + 19 + (3\times19) + 171 = 260$


(d) $\sigma(200) = 1 + 2 + 2^2 + 2^3 + 5 + 5^2 + (2 \times 5) + (2^2 \times 5) + (2^3 \times 5) + (2 \times 5^2) + (2^2 \times 5^2) + 200 = 465 $


at

Exercise (4.5).1

By applying the Lucas–Lehmer test, determine the primality of $M_{13} = 2^{13} - 1$.


The Lucas-Lehmer test states that the Mersenne number $M_p = 2^p - 1$ is prime if and only if $S_{p−2} \equiv 0 \pmod {M_p}$ where $S_k$ is defined as the least non-negative residue such that $S_0 = 4$ and $S_k ≡ S^2_{k−1}− 2 \pmod {M_p}$ for integer $k \ge 1$.


This definition is recursive. We'll start with

$$ S_0 = 4 $$

Noting $M_{13}=2^{13}-1 = 8191$, we then have

$$ \begin{align} S_1 & \equiv S^2_{0} -2 \pmod {8191} \\ \\ & \equiv (4)^2 -2 \pmod {8191} \\ \\ & \equiv 14 \pmod {8191} \end{align} $$

Continuing

$$ \begin{align} S_2 & \equiv S^2_{1} -2 \pmod {8191} \\ \\ & \equiv (14)^2 -2 \pmod {M_{13}} \\ \\ & \equiv 194 \pmod {8191} \end{align} $$

Similarly

$$ \begin{align} S_4 & \equiv 37634 \pmod {8191} \\ \\ & \equiv 4870 \pmod {8191} \end{align} $$

We continue in this manner until $S_{11}$

kS_k
04
114
2194
34870
43953
55970
61857
736
81294
93470
10128
110


We have shown $S_{11} \equiv 0 \pmod {8191}$, which means $M_{13}=2^{13}-1$ is prime.


at

Tuesday, 27 January 2026

Exercise (4.4).18

Prove Proposition (4.23).

You may find the result of Supplementary Problems 3, question 15 useful:

Let $\gcd (a, n) = 1$ and $k$ be the smallest positive integer such that $a^k \equiv 1 \pmod {n}$ .

Then $a^h \equiv 1 \pmod {n} \iff k \mid  h$.


Let's remind ourselves of Proposition (4.23).

Let $q$ be an odd prime. Any prime factor $p$ of the composite Mersenne number $M_q = 2^q- 1$ is of the form $p= 2kq + 1$ where $k$ is an integer.


The smallest odd prime $q$ is 3, and so the smallest prime $p$ is 7, which means $\gcd(p,2)=1$. This allows us to use Fermat's Little Theorem (4.1) to give

$$ 2^{p-1} \equiv 1 \pmod p $$

Assuming $p$ is a factor of $2^q -1$ also gives us

$$ 2^q \equiv 1 \pmod p $$


We want to show $q$ is the smallest positive integer such that $2^q \equiv 1 \pmod p$. Let's assume there is another integer $s$ which is the smallest integer such that $2^s \equiv 1 \pmod p$. Using the given result, for some integer $j$, we have

$$ s \mid sj \quad \iff \quad 2^{sj} \equiv 1 \pmod p $$

Comparing this to $2^q \equiv 1 \pmod p$, noting that $q=sj$ is prime, means the smallest positive integer $s=q$. The other option $s=1$ is not possible because $2^1\equiv 1 \pmod p$ is a contradiction.


Having establishing $q$ is the smallest positive integer such that $2^q \equiv 1 \pmod p$ and comparing with $2^{p-1} \equiv 1 \pmod p$, the given result tells us

$$ 2^{p-1} \equiv 1 \pmod p \quad \iff \quad q \mid p-1 $$

That is, for some integer $n$, 

$$ qn = p - 1 $$

Re-arranging

$$ p = qn + 1 $$

Since both $p$ and $q$ are odd primes, $n$ must be even, so we can write it as $n=2k$.

This gives us the desired conclusion

$$ p = 2kq + 1 $$


at

Monday, 26 January 2026

Exercise (4.4).17

Show that 41 is a Germain prime.

Explain why $(2 × 41) + 1 = 83$ is not a factor of $2^{41}− 1$.


41 is a Germain prime if 41 is prime, and $2(41)+1$ is prime.

41 is prime. $2(41)+1=83$ is also prime. 

And so 41 is a Germain prime.


Corollary (4.21) states that if Germain prime $q \equiv 1 \pmod 4$ then $2q+1 \mid 2^q+1$. 

In our case, $41 \equiv 1 \pmod 4$, and so $83 \mid 2^{41}+1$.

This means, for some integer $k$

$$ \begin{align} 83k & = 2^{41}+1 \\ \\  83k-2 & = 2^{41}-1 \\ \\ 83(k-\frac{2}{83}) & = 2^{41}-1  \end{align} $$

This shows that 83 is not a factor of $2^{41}-1$, because there is no integer $k$ for which $(k-\frac{2}{83})$ is an integer. 


at

Exercise (4.4).16

(a) Let $8p + 7$ be prime where $p \ge 1$. Prove that $2^{4p+3}- 1$ is composite.

(b) Let $q= 4n− 1$ and $p= 8n− 1$ both be prime for $n > 1$. Prove that $p \mid (2^q - 1)$.


(a) We consider two cases for $(4p+3)$. It is either composite or prime.

Case $(4p+3)$ is composite

Corollary (4.11) tells us that if $n$ is composite, so is $2^n-1$. If $(4p+3)$ is composite, so is $2^{4p+3}-1$.

Case $(4p+3)$ is prime

If $(4p+3)$ is prime, then $2(4p+3)+1=8p+7$, which we're given as prime. And so $(4p+3)$ is a Germain prime.

Proposition (4.22) says that if $q \ne 3$ is Germain prime, and $q \equiv -1 \pmod 4$ then $M_q=2^q-1$ is composite. We do have $4p+3 \equiv -1 \pmod 4$, and we have $4p+3 \ge 7 \ne 3$ , and so $2^{4p+3}-1$ is composite.

Both cases conclude $2^{4p+3}-1$ is composite.


(b) We have $q=4n-1$ is prime. We also have $p = 2q + 1 = 8n-1$ is prime. This means $q$ is a Germain prime.

Since $q \equiv -1 \pmod 4$, and $q > 4(1)-1 \ne 3$, by Proposition (4.22) we have $p \mid (2^q-1)$.


at

Sunday, 25 January 2026

Exercise (4.4).15

Prove that if $n > 1$ is not a power of 2 then $2^n + 1$ is a composite integer.

Note that if $n$ is a power of 2 then $2^n + 1$ is a Fermat number.

Hint: If $n$ is odd then we have the following result:

$$ x^n + 1 = (x + 1) (x^{n-1} - x^{n-2} + x^{n-3} - x^{n-4} + \ldots - x + 1)$$


Let's write $n=ab$ where $a=2^k$ are any prime factors 2 with multiplicity $k$, and $b$ is the remaining odd factor. 


If $b=1$ then $n$ is a power of 2, a case which is excluded. Since $b$ is odd, we have $b \ge 3$.


Using the hint, since $b$ is odd, we have

$$ \begin{align} 2^n + 1 & = 2^{ab} + 1 \\ \\ & = (2^a)^b + 1 \\ \\ & = (2^a+1) \biggl ( (2^a)^{b-1} - (2^a)^{b-2} + (2^a)^{b-3} - \ldots - (2^a) +1 \biggr )  \end{align}$$


We need to show these factors are non-trivial, that is greater than 1, and less than $n$:

  • Since $k \ge 0 \implies a \ge 1$, we have $(2^a +1) \ge 3 > 1$. 
  • Since $b \ge 3$, we have  $n = 2^{ab}+1  \ge 2^{3a}+1 > (2^a + 1)$. 
And so  $(2^a+1)$ is a non-trivial factor of $n$. Incidentally, this also means the other factor is non-trivial.


Given the conditions $n>1$ and is not a power of 2, we have found a non-trivial factor of $2^n+1$. This means $2^n+1$ must be a composite integer.


at

Exercise (4.4).14

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

Step A: A prime factor $p$ of $2^{61}-1$ is of the form

$$p= 122k + 1$$

Step B: With $k = 1$ we have $p = 123$ which is composite.

Step C: With $k = 2$ we have $p = 245$ which is composite.

Step D: With $k = 3$ we have $p = 367$ which is prime.

Step E: $p= 367 ≡ −1 \pmod 8$. Hence $p= 367$ is a prime factor of $2^{61} - 1$.


Step A is correct because 61 is an odd prime.

Steps B-D are correct numerically.

Step E is incorrect. Proposition (4.19)(a) says that a prime $p=2n+1$ for some integer $n$ is a factor of $2^n-1$ if $p \equiv \pm1 \pmod 8$. Here $367 \ne 2(61)+1$.


at

Saturday, 24 January 2026

Exercise (4.4).13

Find a prime factor of $M_{1559} = 2^{1559} - 1$ where the index 1559 is prime.


We're given 1559 is an odd prime, so we can try using Propositions (4.23) and (4.24) to find candidate factors. Any prime factor $p$ of $2^q-1$ is of the form $2qk+1$ where $k$ is an integer, and is congruent to $\pm 1 \pmod 8$.

The following table shows candidates that confirm to these constraints.

kP=2*k*(1559)+1p mod 8prime?
131197yes
262375
393553

The first candidate 3119 conforms to the conditions, and a computer algebra systems confirms it divides $M_{1559}$.


So a prime factor of $M_{1559}=2^{1559}-1$ is 3119.


Note: The author's solution uses Proposition (4.21)(a) which is simpler.


at

Exercise (4.4).12

(i) Show that 239 is a Germain prime.

(ii) Show that $2^{239} - 1$ is a composite Mersenne number. Find a prime factor of $2^{239} - 1$.

(iii) Find another prime factor of $2^{239} − 1$.


(i) 239 is a Germain prime if it is a prime itself, and $2(239)+1=479$ is also a prime.

Both 239 and 479 are prime, and so 239 is a Germain prime.


(ii) Sine $p=239$ is a Germain prime, and $p \equiv -1 \pmod 4$, then by Corollary (4.21)(a) we have $p \mid 2^q -1$, where $q=2p+1$.

That is, $479 \mid 2^{239}-1$. And so $M_{239}=2^{239}-1$ is composite with a prime factor 479.


(iii) We use Propositions (4.23) and (4.24) to constrain the candidates for prime factors. If $q$ is an odd prime, then any prime factor of $2^1-1$ must be of the form $2qk+1$ for some integer $k$, and also be congruent to $\pm1 \pmod 8$.

The following table shows possible candidates.

kp =2 *(239)*k+1p mod 8prime?
14797yes
29575
314353
419131yes

We can see that prime 1913 conforms to the two conditions, so is a candidate.

Using computer algebra software, we confirm that 1913 divides $2^{239}-1$.

And so another factor of $2^{239}-1$ is 1913.


at

Exercise (4.4).11

Show that the following integers are composite by finding a prime factor:

(a) $2^{41} + 1$

(b) $2^{53} + 1$


(a) $q=41$ is a Germain prime, because $p=2(41)+1=83$ is a prime. 

Also, $q \equiv 1 \pmod 4$, and so by Corollary (4.21)(b) we have $p \mid 2^q +1$. That is

$$ 83 \mid 2^{41} + 1 $$

So $2^{41} + 1$ is composite with a prime factor 83.


(b) $q=53$ is a Germain prime, because $p=2(53)+1=107$ is a prime. 

Also, $q \equiv 1 \pmod 4$, and so by Corollary (4.21)(b) we have $p \mid 2^q +1$. That is

$$ 107 \mid 2^{53} + 1 $$

So $2^{53} + 1$ is composite with a prime factor 107.


at

Exercise (4.4).10

Prove Proposition (4.22).


Proposition (4.22):

If $q \ne 3$ is a Germain prime and $q \equiv -1 \pmod 4$ then the Mersenne number $M_q = 2^q - 1$ is composite and $p \mid  (2^q - 1)$ where $p=2q + 1$.


We're given $q \ne 3$ is a Germain prime. This means $p=2q+1$ is also prime.

We're also given $q \equiv -1 \pmod 4$, so by Corollary (4.21) we have $p \mid 2^q -1$.


We need to show that $p$ is a non-trivial factor of $2^q-1$, that is, $p<2^q-1$.

$$ \begin{align} p  & < 2^q -1 \\ \\ 2q + 1&  < 2^q -1 \\ \\ 2(q+1) & < 2^q \end{align} $$

This is true for Germain primes $q>3$. The Germain prime $q=3$ is excluded specifically, and $q=2$ is ruled out because $q \not \equiv -1 \pmod 4$.


And so $p$ is a non-trivial prime factor of $2^q-1$, meaning $M_q$ is composite, proving Proposition (4.22).


at

Exercise (4.4).9

Prove Corollary (4.21) (b).


Corollary (4.21)(b) is

Let $q$ and $p= 2q + 1$ both be primes. Note that $q$ is a Germain prime.

(b) If $q \equiv 1 \pmod 4$ then $p \mid (2^q + 1)$.


We'll make use of Proposition (4.19)(b)

Let $p= 2n + 1$ be prime. Then

(b) If $p \equiv \pm 3 \pmod 8$ then $p \mid (2^n + 1)$.


We start with Germain prime $q \equiv 1 \pmod 4$. This means, for some integer $k$,

$$ q = 1 + 4k $$

Then prime $p=2q +1$ becomes

$$ \begin{align} p &= 2(1 + 4k) + 1 \\ \\ & = 3 + 8k \end{align} $$

And so $p \equiv 3 \pmod 8$. 

By Proposition (4.19)(b), setting $q=n$, this means $p \mid (2^q+1)$.


And so Corollary (4.21)(b) is proven.


at

Exercise (4.4).8

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

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

$$q= (2 × 49 × k) + 1 = 98k + 1$$

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

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

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


Step A is incorrect.

Proposition (4.23) requires the index of 2 to be an odd prime. Here 49 is not a prime.


at

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


at

Exercise (4.4).6

Show that the following are prime:

(a) $M_{13} = 2^{13} - 1$

(b) $M_{17} = 2^{17}− 1$


(a) Any prime factor of $M_{13}$ must be less than or equal to $\lfloor \sqrt{2^{13}-1} \rfloor = 90$. So we only need to test factors up to 90.

By Proposition 4.23, we know that any prime factor $p$ must be of the form $p=2k(13)+1$, where $k$ is an integer.

By Proposition 4.24, we know that any prime factor must be congruent to $\pm 1 \pmod 8$.

The following table lists the primes up to 90, and tests their conformance to these two conditions.

p(p-1) mod (2*13)p mod 8
212
323
545
767
11103
13125
17161
19183
23227
2925
3147
37105
41141
43163
47207
5305
5963
6185
67143
71187
73201
7907
8343
89101
97181

We can see that only prime $p=79$ conforms to these 2 conditions, and so is the only candidate.

However, using a calculator we can see that $79$ does not divide $2^{13}-1$.

These leaves no candidates as a prime factor of $M_{13}$ and so it is a prime itself.


(b) Any prime factor of $M_{17}$ must be less than or equal to $\lfloor \sqrt{2^{17}-1} \rfloor = 362$. So we only need to test factors up to 362.

By Proposition 4.23, we know that any prime factor $p$ must be of the form $p=2k(17)+1$, where $k$ is an integer.

By Proposition 4.24, we know that any prime factor must be congruent to $\pm 1 \pmod 8$.

The following table shows only the primes up to 90, which confirm to these two tests.

p(p-1) mod (2*17)p mod 8
10307
13701
23907

Using a calculator, we can see that none of these primes 103, 137, and 239 divide $M_{17}$.

Since there are no remaining candidates, $M_{17}$ is a prime.


at

Exercise (4.4).5

Show that $78511$ (prime) is a factor of the composite Mersenne number $2^{2617}− 1$.


2617 is prime. By Proposition (4.23) any prime factor $p$ of $2^{2617}-1$ is of the form $p=2k(2617)+1$, where $k$ is an integer. The prime $78511=2(2617)(15)+1$, and so is not ruled out as a candidate.

Also, $78511 \equiv -1 \pmod 8$, so by Proposition (4.24) is not ruled out as a candidate.

We can use computer algebra software to confirm 78511 is a prime factor of $M_{2617}$.


Note: the author's solution suggest conforming to Propositions (4.23) and (4.24) is sufficient to conclude 78511 is a prime factor, but that is not correct. The propositions provide necessary but not sufficient conditions.


at

Exercise (4.4).4

Find a prime factor of the composite Mersenne number $M_{79}$.

(You will need to be persistent to find a factor of this number.)


We first note that $q=79$ is prime. However $p=2(79)+1=159$ is not prime. 

So we  turn to Propositions (4.23) and (4.24).

Proposition (4.23).  Let $q$ be an odd prime. Any prime factor $p$ of the composite Mersenne $M_q = 2^q− 1$ is of the form $p= 2kq + 1$ where $k$ is an integer.

Proposition (4.24). Let $q$ be an odd prime. Any prime factor $p$ of $M_q = 2^q -1 $ is of the form $p \equiv \pm 1 \pmod 8$. 


The following table shows examples of $p=2k(79)+1$, whether it is prime, and its congruence modulo 8.

kp=2k(79)+1prime?p mod 8
1159no7
2317yes5
3475no3
4633no1
5791no7
6949no5
71107no3
81265no1
91423yes7
101581no5
111739no3
121897no1
132055no7
142213yes5
152371no3
162529no1
172687yes7
182845no5

We can see $p=1423$ is a candidate since it is a prime the form $2kq+1$ and is congruent to -1 modulo 8. However it does not divide $M_{79}$.

We can see another candidate $p=2687$ which his prime, of the form $2qk+1$, and is congruent to -1 modulo 8. This does divide $M_{79}$.

So 2687 is a prime factor of $M_{79}$.


at

Exercise (4.4).3

Find a prime factor of the following Mersenne numbers $M_q$:

(a) $M_{83}$

(b) $M_{131}$

(c) $M_{179}$

(d) $M_{191}$


(a) Setting $q=83$ gives $p=2(83)+1 = 167$ which is prime. Since $q=83$ is also prime, then $83$ is a Germain prime. 

As $q \equiv -1 \pmod 4$, by Corollary (4.21) we have $167 \mid 2^{83}-1$.

That is, 167 is a prime factor of $M_{83}$.


(b) Setting $q=131$ gives $p=2(131)+1)=263$. Both 131 and 263 are prime, and so 131 is a Germain prime.

As $q \equiv -1 \pmod 4$, by Corollary (4.21) we have $263 \mid 2^{131}-1 $.

That is, 263 is a prime factor of $M_{131}$.


(c) Setting $q=179$ gives $p=2(179)+1=359$. Both 179 and 359 are prime, and so 179 is a Germain prime.

As $q \equiv -1 \pmod 4$, by Corollary (4.21) we have $359 \mid 2^{179}-1$.

That is, 359 is a prime factor of $M_{179}$.


(d) Setting $q=191$, gives $p=2(191)+1=383$. Both 191 and 383 are prime, and so 191 is a Germain prime.

As $q \equiv -1 \pmod 4$, by Corollary (4.21) we have $383 \mid 2^{191}-1$.

That is, 383 is a prime factor of $M_{191}$.


at

Friday, 23 January 2026

Exercise (4.4).2

Determine a prime factor of the following composite Mersenne numbers $M_q$:

(a) $M_{43}$

(b) $M_{73}$


We remind ourselves of Proposition (4.23).  Let $q$ be an odd prime. Any prime factor $p$ of the composite Mersenne $M_q = 2^q− 1$ is of the form $p= 2kq + 1$ where $k$ is an integer.

Note that this does not mean all primes of the form $p=2kq+$ are factors of $M_q$. It means that those that are factors, have this form. That is, factor implies form, not form implies factor.


We also remind ourselves of Proposition (4.24). Let $q$ be an odd prime. Any prime factor $p$ of $M_q = 2^q -1 $ is of the form $p \equiv \pm 1 \pmod 8$. 

Again, this not mean all primes of the form are factors, only that factors have this form.


(a) $M_{43}=2^{43}-1$. 

We can't use Proposition (4.19)(a), because setting $n=43$ gives $p=2(43)+1=87$ which is not prime. 

We can't use Corollary (4.21) because $43$ is not a Germain prime as $2(43)+1=87$ is not prime.

Let's try finding candidates that conform to propositions (4.23) and (4.24), which are necessary but not sufficient conditions.

The following table shows values of $p=2k(43)+1$, whether it is prime, and $p \mod 8$.

kp=2k(43)+1prime?p mod 8
187no7
2173yes5
3259no3
4345no1
5431yes7
6517no5
7603no3

We can see $k=5$ gives $p=431$, which is prime, and is congruent to -1 modulo 8, and so is a candidate factor of $2^{43}-1$.

Using a calculator confirms that $431 \mid 2^{43}-1$. And so 431 is a prime factor of $2^{43}-1$.


(b) $M_{73}=2^{43}-1$. 

We can't use Proposition (4.19)(a), because setting $n=73$ gives $p=2(73)+1=147$ which is not prime. 

We can't use Corollary (4.21) because $73$ is not a Germain prime as $2(73)+1=147$ is not prime.

Let's try finding candidates that conform to propositions (4.23) and (4.24), which are necessary but not sufficient conditions.

The following table shows values of $p=2k(73)+1$, whether it is prime, and $p \mod 8$.

kp=2k(73)+1prime?p mod 8
1147no3
2293yes5
3439yes7
4585no1
5731no3
6877yes5
71023no7

We can see $k=3$ gives $p=439$, which is prime and also congruent to -1 modulo 8, an so is a candidate factor of $2^{73}-1$.

Using a computer algebra system (link) confirms $439 \mid 2^{73}-1$. And so 439 is a prime factor of $2^{73}-1$.


Note: The author's solutions suggest that a number that conforms to propositions (4.23) and (4.24) is a prime factor. This is not correct. The propositions provide necessary but not sufficient conditions for a prime factor of a Mersenne number.


at

Thursday, 22 January 2026

Exercise (4.4).1

Find a prime factor greater than 3 of the following integers:

(a) $2^6 + 1$

(b) $2^{14} + 1$

(c) $2^{15} - 1$

(d) $2^{20} - 1$

(e) $2^{114} + 1$

(f) $2^{504} - 1$


We'll make use of Proposition (4.19) which says that if $p= 2n + 1$ is prime, then

  • $p \equiv \pm 1 \pmod 8 \implies p \mid (2^n− 1)$
  • $p \equiv \pm 3 \pmod 8 \implies p \mid (2^n + 1)$


(a) We have $n=6$, and $p=2n+1= 13$ is prime, and also $13 \equiv -3 \pmod 8$.

By Proposition (4.19) we conclude $13 \mid 2^6 + 1$.


(b) We have $n=14$, and $p=2n+1= 29$ is prime, and also $29 \equiv -3 \pmod 8$.

By Proposition (4.19) we conclude $13 \mid 2^{14} + 1$.


(c) We have $n=15$, and $p=2n+1= 31$ is prime, and also $31 \equiv -1 \pmod 8$.

By Proposition (4.19) we conclude $31 \mid 2^{15} - 1$.


(d) We have $n=20$, and $p=2n+1= 41$ is prime, and also $41 \equiv +1 \pmod 8$.

By Proposition (4.19) we conclude $41 \mid 2^{20} - 1$.


(e) We have $n=114$, and $p=2n+1= 229$ is prime, and also $229 \equiv -3 \pmod 8$.

By Proposition (4.19) we conclude $229 \mid 2^{114} + 1$.


(f) We have $n=504$, and $p=2n+1= 1009$ is prime, and also $1009 \equiv +1 \pmod 8$.

By Proposition (4.19) we conclude $1009 \mid 2^{504} - 1$.


at

Exercise (4.3).21

Show that the following statement is false:

A composite number $n$ is a Carmichael number ⇔ for every prime $p$ which satisfies $p \mid n$ we have $(p− 1) \mid (n− 1)$.

Hint: Consider $n = pk$.


To prove the statement is false we only need one counter-example.


Consider $n = 9$. The prime factorisation is $9 = 3 \times 3$. 

Let's check that the prime 3 satisfies $(p-1) \mid (n-1)$. Here this is, $2 \mid 8$, and so the condition is satisfied.


We now need to show that $9$ is not a Carmichael number. We'll go through the process even though we know 561 is the smallest Carmichael number.

Since we know 9 is composite, to show 9 is a not Carmichael number we need to show that $a^{9-1} \equiv 1 \pmod 9$ is not true for all integers $a$ where $\gcd(a,n)=1$.

If we choose $a=2$, then $\gcd(2,9)=1$ and

$$2^8 \equiv 256 \equiv 4 \not \equiv 1 \pmod 9$$

This means $9$ is not a Carmichael number.


By finding a counter-example of $n=9$ we have shown the statement is false.


at

Wednesday, 21 January 2026

Exercise (4.3).20

Prove that there are infinitely many base 2-pseudoprimes.


If $m$ is a base-2 pseudoprime,  then

  • $m$ is a composite
  • $2^{m-1} \equiv 1 \pmod m$ where $\gcd(m,2)=1$


Let's construct $n$ as

$$n=2^m-1$$

and establish that it is base 2 pseudoprime. To do this we must show

  • $n$ is composite
  • $2^{n-1} \equiv 1 \pmod n$


Since $m$ is given as composite. we can write it as $m=ab$. The difference of powers identity gives us

$$ n = 2^m-1 = 2^{ab}-1 = (2^a-1) \biggl (2^{a(b-1)}+ 2^{a(b-2)} + \ldots + 2^a + 1 \biggr ) $$

And so $n$ is composite too.


We now consider $2^{n-1} \pmod n$. 

We note that $2^{m-1} \equiv 1 \pmod m$ implies $2^m \equiv 2 \pmod m$, or $2^m-2 = km$ for some integer $k$. We also note that $2^m \equiv 1 \pmod n$.

$$ \begin{align} 2^{n-1} & \equiv 2^{2^m-2} \pmod n \\ \\ & \equiv 2^{km} \pmod n \\ \\ & \equiv (2^m)^k \pmod n \\ \\ & \equiv (1)^k \pmod n \\ \\ & \equiv 1 \pmod n \end{align} $$

We've shown $2^{n-1} \equiv 1 \pmod n$.


And so $n=2^m-1$ is also a pseudoprime.


If $m$ is a base 2 pseudoprime, we can always construct another base 2 pseudoprime $n=2^m-1$. Since $n>m$ for $m>1$, we can repeat the process endlessly, and generate endless base 2 pseudoprimes. To complete the argument, we need to show that a pseudoprime greater than 1 exists, and we have already seen 341 is a base 2 pseudoprime.


Note: The author's solution males use of Proposition (4.13) that if $n$ is a base 2 pseudoprime then $2^n-1$ is also a base 2 pseudoprime. This makes the proof much shorter.


at

Exercise (4.3).19

Show that if the Fermat number $F_n =  2^{2^n} + 1$ is a composite integer then $F_n =  2^{2^n} + 1$ is a base 2-pseudoprime.


To show that $F_n$ is a base 2 pseudoprime, we need to show

  • $F_n$ is composite
  • $2^{F_n-1} \equiv 1 \pmod {F_n}$


We are assuming $F_n$ is composite.


By definition $F_n \equiv 0 \pmod {F_n}$, that is, $2^{2^n}+1 \equiv 0 \pmod {2^{2^n}+1}$. And so

$$ 2^{2^n}  \equiv -1 \pmod {F_n} $$


Can we raise $2^{2^n}$ to a power $k$ such that the result is $2^{F_n-1} = 2^{2^{2^n}}$ ?

$$ \begin{align} (2^{2^n})^k & =  2^{2^{2^n}} \\ \\ 2^{k \times 2^n} & =  2^{2^{2^n}} \\ \\ k \times 2^n & =  2^{2^n} \\ \\ k & = 2^{(2^n-n)} \end{align} $$


And so, using Proposition (3.8) that $a \equiv b \pmod n \implies a^m \equiv b^m \pmod n $, for natural $m$, we have

$$ \begin{align} 2^{2^n} &  \equiv -1 \pmod {F_n}  \\ \\ (2^{2^n})^k & \equiv (-1)^k \pmod {F_n} \\ \\ 2^{F_n-1} & \equiv (-1)^{2^{(2^n-n)}} \pmod {F_n} \\ \\ & \equiv 1 \pmod {F_n} \end{align} $$


We have shown that $2^{F_n-1} \equiv 1 \pmod {F_n}$, which means $F_n$ is a base 2 pseudoprime, if $F_n$ is composite.


at

Exercise (4.3).18

(a) Show that 25 is a base 7-pseudoprime but not a Carmichael number.

(b) Show that 217 is a base 5-pseudoprime but not a Carmichael number.


(a) To show 25 us a base 7 pseudoprime but not a Carmichael number, we need to show:

  • 25 is composite
  • $7^{25-1} \equiv 1 \pmod {25}$
  • A counterexample $x$ where $x^{25-1} \not \equiv 1 \pmod {25}$ where $\gcd(25,x)=1$


$25=5\times5$ and so 25 is composite.


Using $7^4 \equiv 2401 \equiv 1 \pmod {25}$, we have

$$ \begin{align} 7^{25-1} & \equiv (7^4)^6 \pmod {25} \\ \\ & \equiv 1^6 \pmod {25} \\ \\ & \equiv 1 \pmod{25}  \end{align} $$


Using $x \equiv 3 \pmod{25}$, which is coprime to 25, we have $3^3 \equiv 2 \pmod {25}$, and so

$$ \begin{align} 3^{25-1} & \equiv (3^3)^8 \pmod {25} \\ \\ & \equiv 2^8 \pmod {25} \\ \\ & \equiv 6 \pmod{25} \\ \\ & \not \equiv 1 \pmod{25}  \end{align} $$


And so 25 is a base 7 pseudoprime but not a Carmichael number.



(b) To show 217 us a base 5 pseudoprime but not a Carmichael number, we need to show:

  • 217 is composite
  • $5^{217-1} \equiv 1 \pmod {217}$
  • A counterexample $x$ where $x^{217-1} \not \equiv 1 \pmod {217}$ where $\gcd(217,x)=1$


$217=7\times31$ and so 217 is composite.


Using $5^6 \equiv 15625 \equiv 1 \pmod {217}$, we have

$$ \begin{align} 5^{217-1} & \equiv (5^6)^{36} \pmod {217} \\ \\ & \equiv 1^{36} \pmod {217} \\ \\ & \equiv 1 \pmod{217}  \end{align} $$


Using $x \equiv 4 \pmod{217}$, which is coprime to 217, we have $4^8 \equiv 2 \pmod {217}$, and so

$$ \begin{align} 4^{217-1} & \equiv (4^8)^{27} \pmod {217} \\ \\ & \equiv 2^{27} \pmod {217} \\ \\ & \equiv (2^3)^9 \pmod {217}\\ \\ & \equiv 190 \pmod{217} \\ \\ & \not \equiv 1 \pmod{217}  \end{align} $$


And so 217 is a base 5 pseudoprime but not a Carmichael number.


at

Exercise (4.3).17

Explain why $2^n \mid  2^{2^n}$.


We first note that

$$\begin{align} 2^n & = \underbrace{2 \times 2 \times \ldots \times 2}_{n \text{ prime factors 2}} \\ \\ 2^{2^n} & = \underbrace{2 \times 2 \times \ldots \times 2}_{2^n \text{ prime factor 2}} \end{align}$$


Both $2^n$ and $2^{2^n}$ consist of only of prime factors 2. 

To show that $2^n \mid  2^{2^n}$ we need to show that the number of prime factors $2^n$ is more than or equal to $n$.

We will show $2^n \ge n$ by induction.


Base case $n=0$

$2^n = 2^0 = 1 \ge 0 = n$, and so $2^n \ge n$ is true for the base case $n=0$.


Induction Step $2^n \ge n \implies 2^{n+1} \ge n+1$

The induction hypothesis is that $2^n \ge n$, and we aim to show $2^{n+1} \ge n+1$.

$$ \begin{align} 2^{n+1} & = 2(2^n) \\ \\ & \ge 2 (n) \quad \text{induction hypothesis} \\ \\ & = n + n \\ \\ & \ge n + 1 \quad \text{for } n>0  \end{align} $$

We have shown $2^n \ge n \implies 2^{n+1} \ge n+1$.  The condition $n>0$ is valid as $n=0$ was handled in the base case.


By induction we have shown that the number of prime factors 2 in $2^{2^n}$ is greater than or equal to the number of prime factors 2 in $2^n$, and so $2^n \mid  2^{2^n}$.


at

Tuesday, 20 January 2026

Exercise (4.3).16

Show that in general

$$ (2^{2^n}-1) \not \mid (2^{2^n}+1) $$


Note: The author's solution suggests the question is not accurately phrased. That solution suggests it should say "show that $ (2^{2^n}-1) \mid (2^{2^n}+1) $ is not true in general". In this case a single counter-example is sufficient.


We can show $(2^{2^n}-1) \mid (2^{2^n}+1)$ does not hold in general by finding a counter-example.

Consider $n=1$, then $2^n=2$. This gives us $2^{2^n}-1=3$ and $2^{2^n}+1=5$.

Here $3$ does not divide $5$, and so the given statement does not hold in general.



The interpretation of the question, as given, is that $ (2^{2^n}-1) \not \mid (2^{2^n}+1) $ is true for all natural numbers $n$.


By definition, $x + 1\equiv 2 \pmod {x-1}$ for integer any $x \ge 3$.


For natural number $n \ge 1$, we have $2^n \ge 2$, and so $2^{2^n} \ge 4 \ge 3$.

This means, for $n \ge 1$, 

$$ 2^{2^n}+1 \equiv 2 \pmod {2^{2^n}-1} $$

The congruence 2 means $2^{2^n}+1 \not \mid {2^{2^n}-1}$.


at

Exercise (4.3).15

Prove that if $(2^m-1) \mid (2^n-1)$ then $m \mid n$.


Since $m \ge 1$, we can use the Division Algorithm (1.7) to write

$$n=mq+r$$

where $q$ and $0 \le r < m$ are unique.


Let's write $2^n-1$ as follows

$$ \begin{align} 2^n -1 & = (2^{qm+r} - 2^r)  + (2^r - 1) \\ \\ & = 2^r(2^{qm} - 1) + (2^r -1) \end{align}$$

By definition $m \mid qm$ and so by Proposition (4.9) we have $(2^m-1) \mid (2^{qm}-1)$. This means, for some integer $k$, we have $k(2^m-1) = (2^{mq}-1)$. And so

$$ 2^n -1 = k2^r(2^{m} - 1) + (2^r -1) $$


If we assume $(2^m-1) \mid (2^n-1)$, then

$$ (2^m-1) \mid (2^n-1) \implies (2^m-1) \mid k2^r(2^{m} - 1) + (2^r -1)  $$

This means $2^m-1 \mid 2^r-1$. 


But from the division algorithm $r < m$, and so $2^r-1 < 2^m-1$. The only way  $2^m-1 \mid 2^r-1$ is if $2^r-1=0$. This means $r=0$. And so $n=mq+0 = mq$. This gives u the desired conclusion

$$ (2^m-1) \mid (2^n-1) \implies m \mid q $$


at

Sunday, 18 January 2026

Exercise (4.3).14

Prove that if $2^p− 1$ is composite where $p$ is prime then $2^p− 1$ is a base 2-pseudoprime.


The integer $2^p-1$ is a base 2 pseudoprime if both of the following are true

  • $2^p-1$ is composite
  • $2^{2^p-2} \equiv 1 \pmod {2^p-1}$ for $\gcd(2,2^p-1)=1$

We're given that $2^p-1$ is composite, so we only need to show the second condition.


We first note that $p=2$ is excluded by the antecedent of the statement we want to prove, since $2^2-1=3$ which is not composite. So we only consider $p>2$.


By FlT we have, noting $p \not \mid 2$ since $p>2$, 

$$ \begin{align} 2^{p-1} & \equiv 1 \pmod p \\ \\ 2^{p} & \equiv 2 \pmod p  \end{align}$$

This means, for some integer $k$, we have $2^p-2=kp$.


Noting that $2^p \equiv 1 \pmod {2^p-1}$, we have

$$ \begin{align} 2^{2^p-2} & \equiv 2^{kp} \pmod {2^p-1} \\ \\  & \equiv (2^p)^k \pmod{2^p-1} \\ \\ & \equiv (1)^k  \pmod {2^p-1} \\ \\ & \equiv 1 \pmod {2^p-1}\end{align}$$


By showing that $2^p-1$ is composite, and that $2^{2^p-2} \equiv 1 \pmod {2^p-1}$, we have proved that if that if $2^p− 1$ is composite where $p$ is prime then $2^p− 1$ is a base 2-pseudoprime.


at

Exercise (4.3).13

Prove that if $2^n- 1$ is prime then $n$ is prime.


We'll prove this by proving its contrapositive: if $n$ is composite, then $2^n-1$ is composite.


Assuming $n$ is composite means we can write it as $n=ab$ where $a$ and $b$ are non-trivial factors. Using the difference of powers identity, this means

$$ 2^n -1 = 2^{ab}-1 = (2^a-1) \times \biggl (2^{a(b-1)} + 2^{a(b-2)} + \ldots + 2^a + 1  \biggr )$$

So $2^n-1$ is composite, with a factor $2^a-1$.

By showing 

$$ n \text{ composite } \implies 2^n -1 \text{ composite } $$

we have shown the desired implication

$$ 2^n-1 \text{ prime } \implies n \text{ prime } $$


at

Exercise (4.3).12

Show that 1729 is a Carmichael number.


Let's remind ourselves of Definition (4.14). 

A composite integer $n$ is called a Carmichael number if for every base $a^{n−1} \equiv 1 \pmod n$ provided $\gcd (a, n) = 1$.


We start with the prime decomposition $1729 = 7 \times 13 \times 19$, which also tells us 1729 is composite.

Using FlT we have

$ a^{7-1} \equiv 1 \pmod {7}$ for $\gcd(a,7)=1$

$ a^{13-1} \equiv 1 \pmod {13}$ for $\gcd(a,7)=1$

$ a^{19-1} \equiv 1 \pmod {19}$ for $\gcd(a,7)=1$


We then note

$ a^{1728} \equiv (a^6)^{288} \equiv (1)^{288} \equiv 1 \pmod {7}$ for $\gcd(a,7)=1$

$ a^{1728} \equiv (a^12)^{144} \equiv (1)^{144} \equiv 1 \pmod {13}$ for $\gcd(a,13)=1$

$ a^{1728} \equiv (a^18)^{96} \equiv (1)^{96} \equiv 1 \pmod {17}$ for $\gcd(a,19)=1$


We can then use the result of Ex (3.4)8b to combine these

$$ \begin{align} a^{1729-1} & \equiv 1 \pmod {7 \times 13 \times 19} \\ \\ a^{1729-1} & \equiv 1 \pmod {1729} \end{align}$$


So we have shown that 1729 is composite, and also that $a^{1729-1} \equiv 1 \pmod {1729}$ for all $a$ where $\gcd(a,1729)=1$. And so 1729 is a Carmichael number.


at

Saturday, 17 January 2026

Exercise (4.3).11

Prove Proposition (4.13).


Proposition (4.13) says that if $n$ is a base 2-pseudoprime then $2^n− 1$ is also a base 2-pseudoprime.


We start by assuming that $n$ is a base 2-pseudoprime. This means that both of the following are true

  • $n$ is composite
  • $2^{n-1} \equiv 1 \pmod n$


We need to show both

  • $2^n-1$ is composite
  • $2^{(2^n-2)} \equiv 1 \pmod {2^n-1}$


Since $n$ is composite, Corollary (4.11) which we proved in the previous exercise, tells us that $2^n-1$ is composite.


We know $2^{n-1} \equiv 1 \pmod n$, and so $2^n \equiv 2 \pmod n$, which means for some integer $k$, we have $2^n-2 = kn$. 

$$ \begin{align} 2^{(2^n-2)} & \equiv 2^{kn} \pmod {2^n-1} \\ \\ & \equiv (2^n)^k \pmod {2^n-1} \\ \\ & \equiv (1)^k \pmod {2^n-1} \\ \\ & \equiv 1 \pmod {2^n-1} \end{align} $$

We have shown $2^{2^n-2} \equiv 1 \pmod {2^n-1}$.


And so if $n$ is a base 2-pseudoprime then $2^n− 1$ is also a base 2-pseudoprime.


at

Exercise (4.3).10

Prove Corollary (4.11).


Corollary (4.11) says that if $n$ is composite then $2^n− 1$ is also composite.


We start with Proposition (4.9) which says that, for $m,n$ positive integers

$$ m \mid n \implies (2^m - 1) \mid (2^n-1) $$

This gives us the desired conclusion, because it states that if $n$ is composite, with a non-trivial factor $m$, where $1<m<n$, then $2^n-1$ is composite, with a non-trivial factor $2^m-1$, where $1 < 2^m - 1< 2^n-1 $.


at

Exercise (4.3).7-9

Exercise (4.3).7

Prove that 3 is a factor of $2^{2n}− 1$.


Using Proposition (4.9) we have

$$ 2 \mid 2n \implies (2^{2}-1) \mid (2^{2n}-1) $$

That is, $2^2-1 = 3$ is a factor of $2^{2n}-1$.


Exercise (4.3).8

Prove that 7 is a factor of $2^{3n}-1$.


Using Proposition (4.9) we have

$$ 3 \mid 3n \implies (2^3-1) \mid (2^{3n}-1) $$

That is, $2^3-1=7$ is a factor of $2^{3n}-1$.


Exercise (4.3).9

Prove that 2047 is a factor of $2^{3751}− 1$.


Using Proposition (4.9) we have

$$ 11 \mid 3751 \implies (2^{11}-1) \mid (2^{3751}-1) $$

That is, $2^{11}-1=2047$ is a factor of $2^{3751}-1$.


at

Exercise (4.3).6

What is wrong with the following argument?

$10^5−1 \not \equiv 1 \pmod 5$ implies 5 is composite.


FlT says: 

$$ ( n \text{ prime } \land n \not \mid a ) \quad  \implies \quad a^{n-1} \equiv 1 \pmod n $$


The contrapositive says

$$ a^{n-1} \not \equiv 1 \pmod n \quad \implies \quad (n \text{ composite } \textcolor{red}{ \lor n \mid a} ) $$


So the given statement is incomplete, and should be:

$10^5−1 \not \equiv 1 \pmod 5$ implies 5 is composite or 5 divides 10.


at

Exercise (4.3).5

Factorise the following integers into their prime factors:

(a) $2^{20}− 1$

(b) $2^{21}− 1$

(c) $2^{24}− 1$


(a) We have $20 = 2^2 \times 5$, and so by Proposition (4.9) we have

$$ 2 \mid 20 \implies (2^{2}-1) \mid (2^{20}-1) $$

$$ 5 \mid 20 \implies (2^{5}-1) \mid (2^{20}-1) $$

So two non-trivial factors of $2^{20}-1$ are $2^2-1 =3$ and $2^5-1 = 31$. These are not the only factors.

So far we have

$$ 2^{20}-1 = 3  \times 5^2 \times 13981 $$

By trial and error, we have 11 and 31 as factors too, which leads us to

$$ 2^{20}-1 = 3  \times 5^2 \times 11 \times 31 \times 41 $$


(b) We have $21 = 3 \times 7$, and so by Proposition (4.9) we have

$$ 3 \mid 21 \implies (2^{3}-1) \mid (2^{21}-1) $$

$$ 7 \mid 21 \implies (2^{7}-1) \mid (2^{21}-1) $$

So two non-trivial factors of $2^{21}-1$ are $2^3-1 =7$ and $2^7-1 = 127$. These are not the only factors.

This quickly gives us the required prime factorisation

$$ 2^{21}-1 = 7^2 \times 127 \times 337 $$


(c) We have $24 = 2^3 \times 3$, and so by Proposition (4.9) we have

$$ 2 \mid 24 \implies (2^{2}-1) \mid (2^{24}-1) $$

$$ 3 \mid 24 \implies (2^{3}-1) \mid (2^{24}-1) $$

So two non-trivial factors of $2^{24}-1$ are $2^2-1=3$ and $2^3-1=7$. These are not the only factors.

So we have

$$ 2^{24}-1 = 3^2 \times 7 \times 266305 $$

By experimenting, we have 5 and 13 as factors, leading to a full prime factorisation

$$ 2^{24}-1 = 3^2 \times 5 \times 7 \times 13 \times 17 \times 241 $$


at

Exercise (4.3).4

Show that the following are composite integers by finding a non-trivial factor of each integer:

(a) $2^{123} - 1$

(b) $2^{161051} - 1$

(c) $2^{1769} - 1$


We'll be using Proposition (4.9) which says that for positive integers $m,n$

$$ m \mid n \implies (2^m - 1) \mid (2^n - 1) $$


(a) Using $123=3 \times 41$ we have

$$ 3 \mid 123 \implies (2^{3}-1) \mid (2^{123}-1) $$

So a non-trivial factor is $2^3-1 = 7$.


(b) Using $161051 = 11^5$ we have

$$ 11 \mid 161051 \implies (2^11 - 1) \mid (2^{161051}-1)$$

So a non-trivial factor is $2^11-1 = 2047$


(c) Using $1769=29 \times 61$ we have

$$ 29 \mid 1769 \implies (2^{29}-1) \mid (2^{1769}-1) $$

So a non-trivial factor is $2^{29}-1 = 536870911$.


at

Exercise (4.3).3

(a) Show that 561 is a

(i) base 560-pseudoprime

(ii) base 562-pseudoprime

(b) Show that 91 is not a base2-pseudoprime.


(a)

(i) To show 561 is a base 560 pseudoprime, we need to show both

  • 561 is composite
  • $560^{561-1} \equiv 1 \pmod {561}$

561 is composite since $561 = 3 \times 11 \times 17$.

Also, noting $560 \equiv -1 \pmod {561}$

$$ \begin{align} 560^{561-1} & \equiv (-1)^{560} \pmod {561} \\ \\ & \equiv 1 \pmod {561} \end{align} $$

And so 561 is a base 560 pseudoprime.


(ii) To show 561 is a base 562 pseudoprime, we need to show both

  • 561 is composite
  • $562^{561-1} \equiv 1 \pmod {561}$

561 is composite since $561 = 3 \times 11 \times 17$.

Also, noting $562 \equiv 1 \pmod {561}$

$$ \begin{align} 562^{561-1} & \equiv (1)^{560} \pmod {561} \\ \\ & \equiv 1 \pmod {561} \end{align} $$

And so 562 is a base 560 pseudoprime.


(b) To show 91 is not a base 2 pseudoprime we need to at least one of

  • 91 is prime
  • $2^{91-1} \not \equiv 1 \pmod {91}$

Since $91=7 \times 13$, it is not prime. So we need to show $2^{91-1} \not \equiv 1 \pmod {91}$.

Noting that $2^{12}\equiv 4096 \equiv 1 \pmod {91}$, we have

$$ \begin{align} 2^{91-1} \equiv (2^{12})^7 \times 2^{6} \pmod{91} \\ \\ & \equiv 64 \pmod {91} \\ \\ & \not \equiv 1 \pmod {91} \end {align} $$

And so 91 is not a base 2 pseudoprime.


at

Exercise (4.3).2

Show that 2047 is a base 2-pseudoprime.


To show that a number $n$ is a base $b$-pseudoprime, where $b>1$ and $\gcd(b,n)=1$, we need to show both

  • $n$ is composite
  • $b^{n-1} \equiv 1 \pmod n$


$2047 = 23 \times 89$ and so is composite.


We now show $2^{2047-1} \equiv 1 \pmod {2047}$. We note that $2^{11} \equiv 2048 \equiv 1 \pmod {2047}$.

$$ \begin{align} 2^{2047-1} & \equiv 2^{2046} \pmod {2047} \\ \\ & \equiv (2^{11})^{186}  \pmod {2047}  \\ \\ & \equiv (1)^{186}  \pmod {2047}  \\ \\ & \equiv 1 \pmod {2047} \end{align} $$


We've shown $2^{2047-1} \equiv 1 \pmod {2047}$ and yet 2047 is composite, and so 2047 is a base 2-pseudoprime.


at

Exercise (4.3).1

Verify the following are composite integers by using FlT:

(a) 4097

(b) 32 767

(c) 2197 [use base 13]


Before we start, it is worth reminding ourselves of FlT and its contrapositive. 

FlT says: 

$$ ( n \text{ prime } \land n \not \mid a ) \quad  \implies \quad a^{n-1} \equiv 1 \pmod n $$

The contrapositive says

$$ a^{n-1} \not \equiv 1 \pmod n \quad \implies \quad (n \text{ composite } \lor n \mid a ) $$

If we know $n \not \mid a$, this reduces to

$$ a^{n-1} \not \equiv 1 \pmod n \quad \implies \quad  n \text{ composite } $$

If we know $n$ is an odd integer, then we know $n \not \mid 2$, and so we have the specialised form of Proposition (4.6)

$$ 2^{n-1} \not \equiv 1 \pmod n \quad \implies \quad \text{odd integer } n \text{ composite } $$



(a) Noting that 4097 is an odd integer, and also $2^{12} \equiv 4096 \equiv -1 \pmod {4097}$, we have

$$ \begin{align} 2^{4097-1} & \equiv 2^{4096} \pmod {4097} \\ \\ & \equiv (2^{12})^{341} \times 2^4 \pmod {4097} \\ \\ & \equiv (-1) \times 16 \pmod {4097} \\ \\ & \equiv 4081 \pmod {4097} \\ \\ 2^{4097-1} & \not \equiv 1\pmod {4097} \end{align} $$

So by Proposition (4.6) we conclude 4097 is composite.


(b) Noting that 32767 is an odd integer, and $2^{15} \equiv 32768 \equiv 1 \pmod {32767}$, we have

$$ \begin{align} 2^{32767-1} & \equiv 2^{32766} \pmod {32767} \\ \\ & \equiv (2^{15})^{2184} \times 2^6 \pmod {32767} \\ \\ & \equiv (1) \times 64 \pmod {32767} \\ \\ & \not \equiv 1 \pmod {32767} \end{align} $$

So by Proposition (4.6) we conclude 32767 is composite.


(c) We can immediately see that $13^3=2197$ and so 2197 is composite.


at

Friday, 16 January 2026

Exercise (4.2).18

Let $p$ be an odd prime. Prove that

$$ \left (1 × 3 × 5 × ⋯ × (p− 2) \right )^2 \equiv (−1)^{\frac{p+1}{2}} \pmod p$$


There are two cases to consider, an even number of multiplicands, and an odd number of multiplicands.


Case: Even number of multiplicands.

In this case the sequence of multiplicands is

$$1,\ldots, \frac{p-3}{2}, \frac{p+1}{2}, \ldots, (p-2)$$

And so

$$ \begin{align} \biggl(1 \times 3 \times \ldots \times (p− 2) \biggr )^2 & \equiv \biggl (1 \times 3 \times \ldots (\frac{p-7}{2}) \times (\frac{p-3}{2}) \times (\frac{p+1}{2}) \times (\frac{p+5}{2}) \ldots \times (p-4) \times  (p− 2) \biggr )^2 \pmod p \\ \\ & \equiv \biggl (1 \times 3 \times \ldots (\frac{p-7}{2}) \times (\frac{p-3}{2}) \times (\frac{-p+1}{2})  \times (\frac{-p+5}{2})  \ldots \times (-4) \times  (− 2) \biggr )^2 \pmod p \\ \\ & \equiv \biggl (1 \times 3 \times \ldots (\frac{p-7}{2}) \times (\frac{p-3}{2}) \times (\frac{p-1}{2})  \times (\frac{p-5}{2})  \ldots \times (+4) \times  (+2) \biggr )^2 \pmod p \\ \\   & \equiv \biggl( (\frac{p-1}{2})! \biggr )^2 \pmod p  \end{align} $$



Case: Odd number of multiplicands.

In this case the sequence of multiplicands is

$$1,\ldots, \frac{p-5}{2}, \frac{p-1}{2}, \frac{p+3}{2}, \ldots, (p-2)$$

And so

$$ \begin{align} \biggl(1 \times 3 \times \ldots \times (p− 2) \biggr )^2 & \equiv \biggl (1 \times 3 \times \ldots (\frac{p-5}{2}) \times  (\frac{p-1}{2}) \times (\frac{p+3}{2}) \ldots \times (p-4) \times  (p− 2) \biggr )^2 \pmod p \\ \\  & \equiv \biggl (1 \times 3 \times \ldots (\frac{p-5}{2}) \times  (\frac{p-1}{2}) \times (\frac{-p+3}{2}) \ldots \times (-4) \times  (− 2) \biggr )^2 \pmod p \\ \\ & \equiv \biggl (1 \times 3 \times \ldots (\frac{p-5}{2}) \times  (\frac{p-1}{2}) \times (\frac{p-3}{2}) \ldots \times (+4) \times (+2) \biggr )^2 \pmod p \\ \\ & \equiv \biggl ( (\frac{p-1}{2})!  \biggr)^2 \pmod p \end{align} $$


So in both cases we have

$$  \biggl(1 \times 3 \times \ldots \times (p− 2) \biggr )^2  \equiv  \biggl ( (\frac{p-1}{2})!  \biggr)^2 \pmod p $$

From exercise (4.2).16 we have

$$ -1 \equiv (-1)^{\frac{p-1}{2}} \biggl ( (\frac{p-1}{2})!  \biggr)^2 \pmod p $$

Multiplying both sides by $(-1)^{\frac{p-1}{2}}$

$$  (-1)^{\frac{2}{2}} \times (-1)^{\frac{p-1}{2}} \equiv (-1)^{\frac{p-1}{2}} (-1)^{\frac{p-1}{2}} \biggl ( (\frac{p-1}{2})!  \biggr)^2 \pmod p $$

Noting that $p-1$ is even, and so $(-1)^{\frac{p-1}{2}} (-1)^{\frac{p-1}{2}} \equiv (-1)^{p-1} \equiv 1 \pmod p$.This gives us

$$  (-1)^{\frac{p+1}{2}} \equiv  \biggl ( (\frac{p-1}{2})!  \biggr)^2 \pmod p $$

Which leads immediately to our desired conclusion

$$ \left (1 × 3 × 5 × ⋯ × (p− 2) \right )^2 \equiv (−1)^{\frac{p+1}{2}} \pmod p $$


at

Thursday, 15 January 2026

Exercise (4.2).17

Prove Wilson’s Theorem by using Fermat’s Little Theorem.

Hint: Consider the equation $x^{p−1} − 1 \equiv 0 \pmod p $.


Note: This exercise requires additional knowledge about factorising polynomials (pdf).


If prime $p$ does not divide $x$ then by the FlT, 

$$ x^{p-1} - 1 \equiv 0 \pmod p $$

This means $x \equiv 1, 2, 3, \ldots, p-1 \pmod p$ are solutions of the polynomial congruence $x^{p-1} - 1 \equiv 0 \pmod p$.


Using the factorisation of polynomials (Theorem 4.3 in the linked book), we can factorise the polynomial $x^{p-1} - 1$ modulo $p$ as

$$ x^{p-1} - 1 \equiv (x-1)(x-2)(x-3) \ldots (x-(p-1)) \times Q(x) \pmod p $$

where $Q(x)$ is a polynomial of order 0, that is, a constant. This means $Q(x)=q$, for integer $q$. Comparing coefficients of the left and right hand sides, tells us $q \equiv 1 \pmod p$. And so the factorisation simplifies to

$$ x^{p-1} - 1 \equiv  (x-1)(x-2)(x-3) \ldots (x-(p-1)) \pmod p $$


When $x=0$ we have the following, which makes use of $(-1)^{p-1} \equiv 1 \pmod p$ for $p>2$, and $(-1)^{1} \equiv 1 \pmod p$ for $p=2$.

$$ \begin{align} 0^{p-1} - 1 &  \equiv  (0-1)(0-2)(0-3) \ldots (0-(p-1)) \pmod p \\ \\ - 1 & \equiv  (-1)^{p-1} (p-1)! \pmod p \\ \\   (p-1)! & \equiv -1 \pmod p \end{align} $$

This is Wilson's Theorem.


at

Friday, 9 January 2026

Exercise (4.2).16

Consider the quadratic congruence $x^2 + 1 \equiv 0 \pmod p$ where $p$ is prime.

Prove that $x^2 + 1 \equiv 0 \pmod p$ has a solution if and only if $p= 2$ or $p \equiv 1 \pmod 4$.


We need to prove both directions.



($\impliedby$)

There are two cases, $p= 2$ and $p \equiv 1 \pmod 4$.


In the case $p=2$, the congruence is $x^2 +1 \equiv 0 \pmod 2$.  This is equivalent to $x^2 \equiv -1 \equiv 1 \pmod 2$. This has a solution, which is $x \equiv 1 \pmod 2$.


In the case $p \equiv 1 \pmod 4$, we have $p = 1 + 4k$ for some integer $k$. This gives $\frac{p-1}{2}=2k$, and even number, which we'll use below.

Before we proceed, we derive a result from Wilson's Theorem.

$$ \begin{align} -1 & \equiv (p-1)! \\ \\ & \equiv 1 \times 2 \times \ldots \frac{p-1}{2} \times \frac{p+1}{2} \ldots \times (p-2) \times (p-1) \pmod p \\ \\ & \equiv \underbrace{1 \times 2 \times \ldots \frac{p-1}{2}}_{\frac{p-1}{2} \text{ multiplicands}} \times \underbrace{ \left ( -\frac{p-1}{2} \right ) \ldots \times (-2) \times (-1)}_{\frac{p-1}{2} \text{ multiplicands}} \pmod p \\ \\ & \equiv (-1)^{\frac{p-1}{2}}\left ( (\frac{p-1}{2})! \right ) ^2 \pmod p \\ \\ & \equiv (-1)^{2k}\left ( (\frac{p-1}{2})! \right )^2  \pmod p \\ \\ & \equiv \left ( (\frac{p-1}{2})! \right )^2 \pmod p \end{align} $$

This gives us a solution to $x^2 \equiv -1 \pmod p$, namely $x \equiv (\frac{p-1}{2})! \pmod p$.


We have shown that in both cases, $p= 2$ and $p \equiv 1 \pmod 4$, the congruence $x^2 \equiv -1 \pmod p$ has a solution.



($\implies$)

The prime $p$ conforms to one of three cases, $p=2$, $p \equiv 1 \pmod 4$ and $p \equiv 3 \pmod 4$. If we show that the final case $p=3 \equiv \pmod 4$ is not possible,  then one of the remaining two cases must hold.

For the purpose of contradiction, we assume $p \equiv 3 \pmod 4$,  that is, $p=3+4k$ for some integer $k$.

Since the prime $p$ does not divide $x$, we can use the FlT. If $p$ did divide $x$ then $x^2 +1  \equiv 0 +1 \equiv 1 \pmod p$ which contradicts the given congruence.

$$ \begin{align} 1 & \equiv x^{p-1} \pmod p  \\ \\ & \equiv x^{2+4k} \pmod p \\ \\ &\equiv  (x^2) \times (x^2)^{2k} \pmod p \\ \\ & \equiv (-1) \times (1) \pmod p \\ \\ 1 & \equiv -1 \pmod p  \end{align}$$

This is a contradiction, so the case $p \equiv 3 \pmod 4$ is not possible.

This leaves us with the desired conclusion that  $p= 2$ or $p \equiv 1 \pmod 4$.



We have shown both directions, $\implies$ and $\impliedby$, and so we conclude the bidirectional implication, $x^2 + 1 \equiv 0 \pmod p$ has a solution if and only if $p= 2$ or $p \equiv 1 \pmod 4$.


at

Tuesday, 6 January 2026

Exercise (4.2).15

Let $p$ be prime. Show that

$$ (p− 1)(p− 2) \ldots (p − n) \equiv (−1)^{n} \; n! \pmod p $$

where $ 1 ≤ n < p$.


We proceed as follows

$$ \begin{align} (p-1) \times (p-2) \times \ldots \times  (p-n) & \equiv \underbrace{(-1) \times (-2) \times \ldots (-n)}_{n \text{ multiplicands}} \pmod p \\ \\ & \equiv (-1)^n \times 1 \times 2 \ldots \times n \pmod p \\ \\  & \equiv (-1)^n \; n! \pmod p \end{align} $$


at

Monday, 5 January 2026

Exercise (4.2).14

Let $p$ be an odd prime. Prove that

$$ 2 (p− 3)! \equiv −1  \pmod p $$


We start with Wilson's Theorem

$$ (p-1)! \equiv -1 \pmod p $$

 That is

$$ (p-1) \times (p-2) \times (p-3)! \equiv -1 \pmod p $$

We note that $(p-1) \equiv -1 \pmod p$.

We also note that $(p-2) \equiv -2 \pmod p$, valid since an odd prime is larger than 2. 

$$ (-1) \times (-2) \times (p-3)! \equiv -1 \pmod p $$

Simplifying gives us the desired result

$$ 2 (p− 3)! \equiv −1  \pmod p $$


at

Exercise (4.2).13

Let $p$ be prime. Prove that

$$ (p− 2)! \equiv 1 \pmod p $$


We start with Wilson's Theorem

$$ (p-1)! \equiv -1 \pmod p $$

That is

$$ (p-1) \times (p-2)! \equiv -1 \pmod p $$

Now, $(p-1) \equiv -1 \pmod p$, so

$$ (-1) \times (p-2)! \equiv -1 \pmod p $$

Multiplying by (-1), gives us the desired result

$$ (p-2)! \equiv 1 \pmod p $$


at

Exercise (4.2).12

Let $p$ be prime and $\gcd (n, p) = 1$.

Prove that

$$ (p− 1)! + n^{p−1} \equiv 0  \pmod p $$


We're given $p$ is prime. By Wilson's Theorem this means

$$ (p-1)! \equiv -1 \pmod p $$

Also, $\gcd(n,p)=1$ means $p$ does not divide $n$, and so Fermat's Little Theorem tell us

$$ n^{p-1} \equiv 1 \pmod p$$

Adding these gives us the desired result.

$$ (p− 1)! + n^{p−1} \equiv -1 + 1 \equiv 0  \pmod p $$


at

Exercise (4.2).11

Show that $x^2 \equiv 1 \pmod {n}  \;\not\!\!\!\implies  x \equiv \pm 1 \pmod {n}$.


We show this with a counter-example.

Consider $x \equiv 3 \pmod 8$. 

$$  3^2 \equiv 9  \equiv 1 \pmod 8 $$

Here $x^2 \equiv 1 \pmod n$, but $x \not \equiv \pm 1 \pmod n$. 


Note that $x^2 \equiv 1 \pmod {n}  \implies  x \equiv \pm 1 \pmod {n}$ only if $n$ is prime, as we have shown in a previous exercise.


at

Exercise (4.2).10

Prove the following:

$$ (n− 1)! \equiv \begin{cases} -1 \pmod n & \text{if $n$ is prime} \\  \\ 2 \pmod n & \text{if $n=4$} \\  \\ 0 \pmod n & \text{for all other cases} \end{cases} $$


Let's consider each case in turn.


Case $n$ prime

If $n$ is prime, then by Wilson's Theorem $(n-1)! \equiv -1 \pmod n$.


Case $n=4$

If $n=4$, then $(n-1)! \equiv 6 \equiv 2 \pmod 4$. This is equivalent to $(n-1)! \equiv 2 \pmod n$ if $n=4$.


Case Other $n$

The remaining case is $n$ composite and $n>4$. Since $n$ is composite, it has two non-trivial factors less than or equal to $(n-1)$. Let's call these $d_1$ and $d_2$. By definition, $n = d_1 \times d_2$. 

There are two cases to consider here: $d_1 \ne d_2$, and $d_1 = d_2$.

Case $d_1 \ne d_2$. 

Since both $d_1$ and $d_2$ are both less than or equal to $(n-1)$,  they both divide $(n-1)!$. This is because they each appear once in the sequence of multiplicands of $(n-1)!$. And so $n=d_1 \times d_2$ divides $(n-1)!$, which gives us the desired $(n-1)! \equiv 0 \pmod n$.

Case $d_1 = d_2$. 

In this case $n=d_1^2 = d_2^2$. Clearly $d_1$ is a factor of $(n-1)!$ since it appears once in the sequence of multiplicands of $(n-1)!$. We need to show that $d_1$ also appears as a factor of another multiplicand. Let's consider $2d_1$. Does this appear in the sequence of multiplicands? It does if $2 d_1 \le (n-1)$, that is $2 d_1 < n$.

We know $2 d_1 < n = d_1 \times d_1$ if $2 < d_1$.This is true for $n >4$, which is the case here. And so $2 d_1$ appears in the sequence of multiplicands. 

We have shown $d_1$ appears as a factor at least twice in $(n-1)!$. That is $n = d_1^2$ divides $(n-1)!$, which gives us the desired $(n-1)! \equiv 0 \pmod n$. 


Note: The author's solution doesn't consider the case that $n$ is a perfect square, $n=d_1^2$.


at
Subscribe to: Comments (Atom)