Exercise (4.2).9

Find the least non-negative residue

$$ \left [ \left ( \frac{29-1}{2} \right )! \right ]^2 \pmod {29}$$

The expression $\left ( \frac{29-1}{2} \right )!$ reduces to $14!$. 

$$ \begin{align} 14 ! & \equiv 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \cdot 11 \cdot 12 \cdot 13 \cdot 14 \pmod {29}  \\ \\  & \equiv (2 \cdot 3 \cdot 5) \cdot (4 \cdot 7) \cdot (6 \cdot 10) \cdot (9 \cdot 13) \cdot (8 \cdot 11) \cdot 12  \cdot 14 \\ \\ & \equiv (1) \cdot (-1) \cdot (2) \cdot (1) \cdot (1) \cdot 12  \cdot 14 \\ \\ & \equiv -12 \cdot (2 \cdot 14) \\ \\ & \equiv -12 \cdot (-1) \\ \\ & \equiv 12 \end{align} $$

And so

$$ (14 !)^2 \equiv 28 \pmod {29} $$

The least non-negative residue is 28.

Exercise (4.2).8

Determine $(n− 1)!  \pmod {n}$ for each of the following $n$:

(a) $n = 15$

(b) $n = 21$

(c) $n = 30$

What do you notice about your results?

(a) Since $n=15$ is not prime, we can't immediately use Wilson's Theorem.

We note that

$ 14! \equiv 0 \pmod 3$ because 3 is a factor of 14!

$ 14! \equiv 0 \pmod 5$ because 5 is a factor of 14!

Using the result from Exercise (3.1).24(d) we have

$$ 14! \equiv 0 \pmod {15} $$

(b) Again, since $n=21$ is not prime, we can't use Wilson's Theorem.

We note that

$ 20! \equiv 0 \pmod 3$ because 3 is a factor of 20!

$ 20! \equiv 0 \pmod 7$ because 7 is a factor of 20!

Using the result from Exercise (3.1).24(d) we have

$$ 20! \equiv 0 \pmod {21} $$

(b) Again, since $n=30$ is not prime, we can't use Wilson's Theorem.

We note that

$ 29! \equiv 0 \pmod 2$ because 2 is a factor of 29!

$ 29! \equiv 0 \pmod 3$ because 3 is a factor of 29!

$ 29! \equiv 0 \pmod 7$ because 7 is a factor of 29!

Using the result from Exercise (3.1).24(d) we have

$$ 29! \equiv 0 \pmod {30}$$

We notice that the expression  $(n− 1)!  \pmod {n}$  is congruent to $0$. This is because the selected $n$ are not prime, and the prime factors of $n$ are factors of $(n-1)!$. This will always be the case because those factors are always less than or equal to $(n-1)$.

Exercise (4.2).7

Determine $61! \pmod {71}$.

We start with Wilson's Theorem

$$ \begin{align} 70! & \equiv -1 \pmod {71} \\ \\  70 \cdot 69 \cdot 68 \cdot 67 \cdot 66 \cdot 65 \cdot 64 \cdot 63 \cdot 62 \cdot 61! & \equiv -1 \cdot -2 \cdot -3 \cdot -4 \cdot -5 \cdot -6  \cdot -7  \cdot -8 \cdot -9 \cdot 61! \pmod {71} \\ \\ & \equiv  -2 \cdot 3 \cdot 4 \cdot 5 \cdot 6  \cdot 7  \cdot 8 \cdot 9 \cdot 61! \pmod {71} \\ \\ & \equiv  -2 \cdot 3 \cdot 4 \cdot 5 \cdot 6  \cdot 7  \cdot (1) \cdot 61! \pmod {71} \\ \\ & \equiv  -2  \cdot 4 \cdot (19)  \cdot 7 \cdot 61! \pmod {71} \\ \\ & \equiv  (-56) \cdot (19) \cdot 61! \pmod {71} \\ \\ & \equiv  (1) \cdot 61! \pmod {71} \\ \\ & \equiv -1 \pmod {71} \\ \\ & \equiv 70 \pmod{71} \end{align} $$

This tells us $61! \equiv 70 \pmod {71}$.

Exercise (4.2).6

Without using a calculator determine the least non-negative residue $x$ such that

$$ 96 × 97 × 98 × 99 × 100 \equiv x \pmod {101} $$

We proceed as follows

$$ \begin{align} 96 \times 97 \times 98 \times 100 & \equiv (-5) \times (-4) \times (-3) \times (-2) \times (-1) \pmod {101}  \\ \\ & \equiv -120 \pmod {101} \\ \\ & \equiv 82 \pmod {101} \end{align} $$

The least non-negative residue is $x=82$.

Exercise (4.2).5

Evaluate the least residue x such that

$$ x \equiv 2 (20!) \pmod {23} $$

Wilson's Theorem gives us a start

$$ \begin{align} 22! \equiv -1 \pmod {23} \\ \\ 22 \times 21 \times 20! \equiv -1 \pmod {23} \\ \\ (-1) \times (-2) \times 20! \equiv -1 \pmod {23} \\ \\ 2 \times 20! \equiv -1 \pmod {23} \end{align}$$

So the least residue is $x=-1$.

Note: the exercises asks for the least reside, not the least non-negative residue, so we interpret this as least magnitude.

Exercise (4.2).4

Find $x$ where $x$ is the least non-negative residue such that

$$ x \equiv 8 × 9 × 10 × 11 × 16×17 × 18 × 19 \pmod {13} $$

We start as follows

$$ \begin{align} x & \equiv  8 \times 9 \times 10 \times 11 \times 16 \times 17 \times 18 \times 19 \pmod {13} \\ \\ & \equiv  (-5) \times (-4) \times (-3) \times (-2) \times 3 \times 4 \times 5 \times 6 \pmod {13} \\ \\ & \equiv  (-5) \times (-1) \times (-2) \times (-1) \times 5 \times 6 \pmod {13} \quad \quad \text{ using } 3 \times 4 \equiv -1  \\ \\ & \equiv  (-2) \times 6 \pmod {13} \quad \quad \text{ using } (-5) \times 5 \equiv 1 \\ \\ & \equiv -12 \pmod {13}\\ \\ & \equiv 1 \pmod {13} \end{align} $$

So the least non-negative residue is $x=1$.

Exercise (4.2).3

Determine the remainder when 25! is divided by 17.

17 is a factor of 25! so the remainder when 25! is divided by 17 is 0.