Exercise (4.1).19

Let $p$ be an odd prime such that $p \not \mid n$. Show that the multiplicative inverse of $n^{\frac{p-1}{2}} \pmod p$ is $n^{\frac{p-1}{2}} \pmod p$.

Let's set $a = n^{\frac{p-1}{2}}$ and $b = n^{\frac{p-1}{2}}$ modulo $p$, and then consider $ab \pmod p$

$$  \begin{align} ab & \equiv n^{\frac{p-1}{2}}  \times n^{\frac{p-1}{2}} \pmod p \\ \\ & \equiv  n^{p-1} \pmod p \\ \\ & \equiv 1 \pmod p \text { using FlT} \end{align}$$

This means $b$ is $a^{-1}$, that is, $n^{\frac{p-1}{2}}$ is its own multiplicative inverse modulo $p$.

Exercise (4.1).18

Prove that if $p \not \mid n$ then

$$ n^{k(p−1)} \equiv 1 \pmod {p}$$

where $p$ is prime and $k$ is a natural number.

Since $p \not \mid n$ we can use the FlT

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

Using $a\equiv b \pmod n \implies a^k \equiv b^k \pmod n$,

$$ (n^{p-1})^k \equiv 1^k \pmod p $$

which simplifies to our desired conclusion.

$$ n^{k(p-1)} \equiv 1 \pmod p $$

Exercise (4.1).17

Show that 

$$ \frac{12n^{13} + 23n}{35} $$

is an integer where $n$ is a natural number.

We follow the same strategy as the previous exercise.

We reformulate the requirement for the fraction to be an integer as a congruence.

$$ 12n^{13} + 23n \equiv 0 \pmod {35} $$

Following the hint we consider modulo 7 and modulo 5.

Using $n^7 \equiv n \pmod 7$, we have

$$ n^{13} \equiv n^7 \times n^6 \equiv n \times n^6 \times n^7 \equiv n \pmod 7 $$

And so

$$ 12n^{13} + 23n \equiv 12n + 23n \equiv 35n \equiv 0 \pmod {7} $$

Using $n^5 \equiv n \pmod 5$, we have

$$ n^{13} \equiv (n^5)^2 \times n^3 \equiv n^2 \times n^3 \equiv n^5 \equiv n \pmod 5 $$

And so

$$ 12n^{13} + 23n \equiv 12n + 23n \equiv 35n \equiv 0 \pmod {5} $$

We have

$$ 12n^{13} + 23n \equiv  0 \pmod {7} $$

$$ 12n^{13} + 23n \equiv  0 \pmod {5} $$

And since $\gcd(5,7)=1$, we conclude

$$ 12n^{13} + 23n \equiv  0 \pmod {35} $$

This is equivalent to the following fraction being an integer, for natural $n$

$$ \frac{12n^{13} + 23n}{35} $$

Exercise (4.1).16

Let $n$ be a natural number. Prove that

$$ \frac{25n^{61} + 52n}{77}$$

is an integer.

Hint: You may find the result of Exercises 3.1, question 24 (d) helpful:

$ a \equiv b \pmod {m_k} \implies a \equiv b \pmod {m_1 \times m_2 \times \ldots  \times  m_n}$

where $k= 1, 2, \ldots , n$ and $\gcd (m_i, m_j) = 1$ for $i \neq j$.

We reformulate the fraction needing to be an integer as a congruence,

$$ 25n^{61} +52n \equiv 0 \pmod {77} $$

Taking the hint, we'll consider modulo 11 and modulo 7.

Using $n^{11} \equiv n \pmod {11}$, we have

$$ n^{61} \equiv (n^{11})^5 \times n^6 \equiv n^5 \times n^6 \equiv  n^{11} \equiv n \pmod {11} $$

And so

$$ 25n^{61} +52n \equiv 25n + 52n \equiv 11 \times 7n \equiv 0 \pmod {11} $$

Using $n^7 \equiv n \pmod 7$ we have

$$ n^{61} \equiv (n^7)^8 \times n^5 \equiv n^8 \times n^5 \equiv n^7 \times n^6 \equiv n \times n^6 \equiv n^7 \equiv n \pmod 7 $$

And so

$$ 25n^{61} +52n \equiv 25n + 52n \equiv 7 \times 11n \equiv 0 \pmod {7} $$

Given

$$ 25n^{61} +52n \equiv 0 \pmod {11} $$

$$ 25n^{61} +52n \equiv 0 \pmod {7} $$

and $\gcd(11,7)=1$ we conclude

$$ 25n^{61} +52n \equiv 0 \pmod {77} $$

which is the same as stating the following fraction is an integer

$$ \frac{25n^{61} + 52n}{77}$$

Exercise (4.1).15

Explain why $1055^{210} \not \equiv 1 \pmod {211}$.

The number 211 is prime.

We note that $1055 = 5 \times 211$. This means 211 is a factor of $1055^{210}$, and so 

$1055^{210} \equiv 0 \pmod {211}$

This is why  $1055^{210} \not \equiv 1 \pmod {211}$.

Exercise (4.1).14

 (i) Show that the product of any three consecutive integers is divisible by 3.

(ii) Show that the product of any three consecutive integers is divisible by 6.

(i) Let $n$ be the smallest of the three consecutive integers, Then we have

$ n(n+)(n+2) \equiv n^3 + 3n^2 + 2n \pmod 3$

There are two cases for $n$. It is either divisible by 3, in which case the product is, and we are done. If it is not, then by Corollary 4.2 we have $n^3 \equiv n \pmod 3$. And so

$ n(n+)(n+2) \equiv (n) + 3n^2 + 2n  \equiv  3(n^2 +n) \equiv 0 \pmod 3$

We have shown the product of three consecutive integers is divisible by 3.

(ii)  Let $n$ be the smallest of the three consecutive integers, Then we have

$ n(n+)(n+2) \equiv n^3 + 3n^2 + 2n \pmod 2$

There are two cases for $n$. It is either divisible by 2, in which case the product is, and we are done. If it is not, then by Corollary 4.2 we have $n^2 \equiv n \pmod 2$. And so

$ n(n+)(n+2) \equiv n(n) + 3n^2 + 2n  \equiv 4n^2 + 2n \equiv 2(2n^2 +n)  \equiv 0 \pmod 3$

We have shown the product of three consecutive integers is divisible by 2.

Since that product is also divisible by 3, and both 3 and 2 are co-prime, so the product is divisible by $2 \times 3 = 6$.

Exercise (4.1).13

Compute the least positive residue $x$ such that

$$ 3^{101} \equiv x  \pmod {103} $$

Since 103 is prime, and does not divide 3, we can use the FlT,

$ 3^{102} \equiv 1 \pmod {103}$

This gives us

$ 3^{102} \equiv 3x \equiv 1 \pmod {103} $

The first positive number that is congruent to 1 mod 103 is 104, but this is not a multiple of 3.

The next one is 207, which is $3 \times 69$. 

And so $x \equiv 69 \pmod {103}$.