Let $n, b, r^∗, t^* \in \mathbb{Z}$, with $0 \lt r^∗ \le n \lt r^∗t^∗$. Then there exist $r, t \in \mathbb{Z}$ with

$r \equiv bt \pmod n$, $\lvert r \rvert \lt r^∗$, and $0 < \lvert t \rvert \lt t^∗$.

Expanded proof from Shoup:

Observe $t^*$ must be at least 2, given $r^∗ \lt r^∗t^∗$.

For $i = 0, \dotsc, r^∗−1$ and $j = 0, \dotsc, t^∗−1$, we define the number $v_{ij} := i − bj$. Since we have defined $r^∗t^∗$ numbers, and $r^∗t^∗ \gt n$, two of these numbers must lie in the same residue class modulo $n$; that is, for some $(i_1, j_1) \ne (i_2, j_2)$, we have $v_{i_1j_1} \equiv v_{i_2j_2} \pmod n$.

But why ? Since the number of possible ($i,j$) pair is $r^*t^* \gt n$, two of them must collide in the same class module n. Alternatively, observe when the $ij$ of $v_{ij}$ is interpreted as the product of $i$ and $j$, the why becomes obvious due to the pigeonhole principle.

Moving on,

$$\begin{aligned} v_{i_1j_1} &\equiv v_{i_2j_2} \pmod n \\ i_1 - bj_1 &\equiv i_2 - bj_2 \pmod n \\ i_1 - i_2 &\equiv bj_1 - bj_2 \pmod n \\ i_1 - i_2 &\equiv b(j_1 - j_2) \pmod n \\ \end{aligned}$$

Setting $r := i_1−i_2$ and $t := j_1−j_2$, this implies:

1. $r \equiv bt \pmod n$, $\lvert r \rvert \lt r^∗$, since both $i_1$ and $i_2$ are less than $r^*$,
2. $\lvert t \rvert \lt t^∗$, since both $j_1$ and $j_2$ are less than $t^*$, and
3. either $r \ne 0$ or $t \ne 0$, since $(i_1, j_1) \ne (i_2, j_2)$.

It only remains to show that $t \ne 0$. Suppose to the contrary that $t = 0$. This would imply that $r \equiv 0 \pmod n$ and $r \ne 0$, which is to say that $r$ is a non-zero multiple of n; however, this is impossible, since $\lvert r \rvert \le r^∗ \le n$.

$\Box$

$$\begin{aligned} \dfrac{d}{dx} \left(f(x) \cdot g(x) \right) &= \displaystyle\lim_{h \to 0} \frac{f(x+h) \cdot g(x+h)-f(x) \cdot g(x)}{h} \\ & = \displaystyle\lim_{h \to 0} \frac{\left(f(x) + h \cdot f'(x)\right)\left(g(x) + h \cdot g'(x)\right)-f(x) \cdot g(x)}{h} \\ &= \displaystyle\lim_{h \to 0} \frac{f(x) \cdot g(x) + h \cdot f'(x) \cdot g(x) + h \cdot g'(x) \cdot f(x) + h^2 \cdot f'(x) \cdot g'(x) - f(x) \cdot g(x)}{h} \\ &= \displaystyle\lim_{h \to 0} \left(f'(x) \cdot g(x) + g'(x) \cdot f(x) + h \cdot f'(x) \cdot g'(x) \right) \\ &= f'(x) \cdot g(x) + g'(x) \cdot f(x) \\ \end{aligned}$$

$\Box$

There exists a subtle non-obvious step above. Can you see it ?

Find all elements of $Z_{19}^*$ of multiplicative order 18.

== Attempt ==

Since 19 is a prime number, $\varphi(19) = 19 - 1 = 18$. Using Euler's theorem, we know that $\alpha^{\varphi(19)} = \alpha^{18} = 1$ for $\alpha \in Z_{19}^*$.

(For a given positive integer $n$, we say that $a \in \mathbb{Z}$ with $gcd(a, n) = 1$ is a primitive root modulo $n$ if the multiplicative order of $a$ modulo $n$ is equal to $\varphi(n)$. Since the multiplicative order 18 is equal to $\varphi(19)$, this exercise is equivalent to finding the primitive roots modulo 19.)

Note that if $\alpha^k = 1$ with $k < 18$, $k$ must divide 18. Since the multiplicative order of 1 is always limited to 1, we only need to check $k$ that divides 18 except 1:

== Python ==

n = 19
ks = [2,3,6,9]    # k that divides 18 except 1
output = []
for i in xrange(2,n):
    primitive_root = True
    for k in ks:
        e = i**k
        if e - e/n*n == 1:
            primitive_root = False
            break;  # multiplicative order less than 18
    if primitive_root:
        output.append(i)
print 'Elements with multiplicative order 18:', output

== Output ==

Elements with multiplicative order 18: [2, 3, 10, 13, 14, 15]

Define $\varphi_2(n)$ to be the number of integers $a \in \{0, \dotsc, n-1\}$ such that $\gcd(a, n) = \gcd(a+1, n) = 1$. Show that if $n = p_1^{e_1} \dotsm p_r^{e_r}$ is the factorization of $n$ into primes, then $\varphi_2(n) = n \prod_{i=1}^r (1 - \frac{2}{p_i})$.

== Attempt ==

First, observe that $\varphi_2(n) = p - 2$ for every prime $p$, since the integers $1, \dotsc, p - 2$ and $1+1, \dotsc, p - 2 + 1$ are not divisible by $p$, and hence are relatively prime to $p$.

Second, let $p$ be a prime and $e$ be a positive integer, we can see that $\varphi_2(p^e) = p^{e-1}(p - 2)$. How ? The integers that are multiple of either $p$ or $(p-1)$ but less than $p^e$ are:

$0, p, 2p, \dotsc, (p^{e-1} - 1) \cdot p, \mspace10pt \text{and}$

$(p-1), 2(p-1), \dotsc, p^{e-1} \cdot (p-1)$

of which there are precisely a total of $2p^{e-1}$. Thus,

$\varphi_2(p^e) = p^e - 2p^{e-1} = p^{e-1}(p - 2)$.

Third, it can be shown using Chinese remainder theorem that if $\{n_i\}_{i=1}^k$ is a pairwise relatively prime family of positive integers, and let $n := \prod_{i=1}^k n_i$, then

$\varphi_2(n) = \prod_{i=1}^k \varphi_2(n_i)$

which implies

$\varphi_2(n) = \varphi_2(p_1^{e_1}) \dotsm \varphi_2(p_r^{e_r})$.

Combining this with the result in step 2, we have:

$\varphi_2(n) = \prod_{i=1}^r p_i^{e-1}(p_i - 2) = n \prod_{i=1}^r (1 - \frac{2}{p_i})$

$\Box$

Show that if $n$ is divisible by $r$ distinct odd primes, then $2^r \mid \varphi(n)$, where $\varphi(n) := \lvert \mathbb{Z_n^*} \rvert$, which is the number of integers between $0$ and $n−1$ that are relatively prime to $n$.

== Attempt ==

Based on Theorem 2.11 of Shoup, we know that if $m = p_1^{e_1} \dotsm p_r^{e_r}$ is the factorization of $m$ into primes, then

$\displaystyle \varphi(m) = \prod_{i=1}^r p_i^{e_i-1}(p_i - 1)$

Given n is divisible by r distinct odd primes, $n = p_1^{e_1} \dotsm p_k^{e_k}$ for $k \ge r$. Furthermore, there must exist at least $r$ distinct odd $p_i$ in

$\displaystyle \varphi(n) = \prod_{i=1}^k p_i^{e_i-1}(p_i - 1)$

Since $(p_i - 1)$ is even when $p_i$ is odd, and there are at least $r$ of them, it follows $2^r \mid \varphi(n)$.

$\Box$

Show that

$\varphi(nm) = \gcd(n,m) \cdot \varphi( lcm(n,m) )$

where $\varphi(n)$ is equal to the number of integers between $0$ and $n-1$ that are relatively prime to n. In short, $\varphi(n) := \lvert \mathbb{Z_n^*} \rvert$. $\varphi$ is also known as the Euler's phi function.

== Attempt ==

In general, let $\{n_i\}_{i=1}^k$ be a pairwise relatively prime family of positive integers, and let $n := \prod_{i=1}^k n_i$. Then

$\varphi(n) = \prod_{i=1}^k \varphi(n_i)$

Furthermore, if $n = p_1^{e_1} \dotsm p_r^{e_r}$ is the factorization of $n$ into primes, then

$\varphi(n) = \prod_{i=1}^r p_i^{e_i-1}(p_i - 1) = n \prod_{i=1}^r (1 - \frac{1}{p_i})$

Let $d := \gcd(n,m)$, $n = n'd$ and $m = m'd$ for some integers $n', m'$. Then

$\varphi(nm) = \varphi(n'm'd^2) = \varphi(n'm') \cdot \varphi(d^2)$

as $\gcd(n'm', d^2) = 1$. Note that

$$\begin{aligned} \varphi(d) &= \prod_{i=1}^r p_i^{e_i-1} (p_i - 1) = d \prod_{i=1}^r (1 - \frac{1}{p_i}) \\ \varphi(d^2) &= \prod_{i=1}^r p_i^{2e_i-1} (p_i - 1) = d^2 \prod_{i=1}^r (1 - \frac{1}{p_i}) \\ \therefore \varphi(d^2) &= d \cdot \varphi(d) \\ \end{aligned}$$

Therefore,

$\varphi(nm) = \varphi(n'm') \cdot d \cdot \varphi(d) = d \cdot \varphi(n'm'd)$

as $\gcd(n'm', d) = 1$. But $n'm'd = lcm(n, m)$. So

$\varphi(nm) = d \cdot \varphi( lcm(n,m) ) = \gcd(n,m) \cdot \varphi( lcm(n,m) )$.

$\Box$

An integer $a$ is called square-free if it is not divisible by the square of any integer greater than 1. Show that:

1. $a$ is square-free if and only if $a = \pm p_1 \dotsc p_r$, where the $p_i$’s are distinct primes;
2. every positive integer $n$ can be expressed uniquely as $n = ab^2$, where $a$ and $b$ are positive integers, and $a$ is square-free.

== Attempt ==

(1) seems to follow directly from the definition. Indeed, if the $p_i$'s are not distinct primes, then by definition there exists $p^e$ in $p_i$'s with $e \ge 2$. In other words, $a$ is not square-free.

Suppose $n$ is square-free. We can let $b := 1$ and $a := n$, so $n = n \cdot 1^2 = ab^2$.

Suppose $n$ is not square-free. Then $\displaystyle n = \prod_{i=1}^{r} p_i$, where there exists $p^e$ in $p_i$'s with $e > 1$. Start with $a := n$ and $c := 1$. For each of the $p^e$ in $p_i$'s with $e > 1$, there are only two possibilities. If $e$ is even, we can set $\displaystyle a := \frac{a}{p^e}$ and $c := {p^e}c$. If $e$ is odd (which must then be $> 2$), we can set $\displaystyle a := \frac{a}{p^{e-1}}$ and $c := {p^{e-1}}c$. Observe $a$ would end up as square-free and is unique, and c will become a product of distinct primes, each with an even exponent. Let $b = \sqrt{c}$, $n = ac = ab^2$.

$\Box$

Let $p$ be an odd prime. Show that $\sum_{\beta \in \mathbb{Z}_p^*} \beta^{-1} = \sum_{\beta \in \mathbb{Z}_p^*} \beta = 0$.

== Attempt ==

Given $p$ is prime, $\mathbb{Z}_p = \mathbb{Z}_p^*$, which means all integers from $1$ to $(p - 1)$ are in $\mathbb{Z}_p^*$. Furthermore, every element has a multiplicative inverse, and is itself a multiplicative inverse of some element. Thus,

$\displaystyle\sum_{\beta \in \mathbb{Z}_p^*} \beta^{-1} = \sum_{\beta \in \mathbb{Z}_p^*} \beta = 1 + \dots + (p-1) = \frac{p(p-1)}{2}$

Given $p$ is an odd prime, $2 \mid (p-1)$. Therefore,

$\displaystyle \lbrack \frac{p(p-1)}{2} \rbrack_p = \lbrack p \rbrack_p = \lbrack 0 \rbrack_p$

$\Box$

Consider any $\alpha \in \mathbb{Z_n} \setminus \mathbb{Z_n^*}$ and $\alpha \ne [0]$. Then we have $\alpha = [a]$ with $d := \gcd(a,n) > 1$. Setting $\beta := [\frac{n}{d}]$, what is $\alpha \beta$ ?

$$\begin{aligned} \alpha & \equiv a \equiv a_1 d\pmod n \mspace20pt \text{ for some } a_1 \in \mathbb{Z_n^*}\\ \beta & \equiv \frac{n}{d} \pmod n \\ \alpha \beta & \equiv a_1 d \frac{n}{d} \equiv a_1 n \pmod n \\ \end{aligned}$$

This means $\alpha \beta$ is a multiple of $n$. Setting $\gamma := [0]$, we see that $\alpha \beta = \alpha \gamma$ but $\beta \ne \gamma$! In contrast, if $d := \gcd(a,n) = 1$, then $\alpha \beta = \alpha \gamma$ and $\beta = [n] = [0] = \gamma$. This stresses that in order for the cancellation law to apply in congruences, it requires $\alpha \in \mathbb{Z_n^*}$.

Let $\{n_i\}_{i=1}^k$ be a pairwise relatively prime family of positive integers. Let $a_1, \dotsc, a_k$ and $b_1, \dotsc, b_k$ be integers, and set $d_i := \gcd(a_i, n_i)$ for $i = 1,\dotsc,k$. Show that there exists an integer $z$ such that $a_iz \equiv b_i \pmod{n_i}$ for $i=1,\dotsc,k$ if and only if $d_i \mid b_i$ for $i=1,\dotsc,k$.

== Attempt ==

$\implies$

In general, for every $b \in \mathbb{Z}$, the congruence $az \equiv b \pmod n$ has a solution $z \in \mathbb{Z}$ if and only if $d \mid b$. Therefore, the only if condition holds.

$\impliedby$

Assume $d_i \mid b_i$, we know there exists a solution $z_i$ such that $a_i z_i \equiv b_i \pmod{n_i}$ for $i=1,\dotsc,k$. In general, for all $z,z′ \in \mathbb{Z}$, we have $az \equiv az′ \pmod n$ if and only if $z \equiv z′ \pmod {\frac{n}{d}}$. Therefore,

$$\begin{aligned} a_i \cdot z_i &\equiv b_i \pmod{n_i} \\ \frac{a_i}{d_i}z_i &\equiv \frac{b_i}{d_i} \pmod{\frac{n_i}{d_i}} \\ \end{aligned}$$

Observe that $\gcd(\frac{a_i}{d_i}, {\frac{n_i}{d_i}}) = 1$, which means there always exists a multiplicative modular inverse $t_i$ such that $\frac{a_i}{d_i}t_i = 1 \pmod{\frac{n_i}{d_i}}$. So,

$$\begin{aligned} \frac{a_i}{d_i} t_i \cdot z_i &\equiv \frac{b_i}{d_i}t_i \pmod{\frac{n_i}{d_i}} \\ z_i &\equiv \frac{b_i}{d_i}t_i \pmod{\frac{n_i}{d_i}} \\ \end{aligned}$$

Observe that given $\{n_i\}_{i=1}^k$ are pairwise relatively prime, so are $\{ \frac{n_i}{d_i} \}_{i=1}^k$. Therefore, by the Chinese remainder theorem, we know there exists a solution $z \in \mathbb{Z}$ that satisfies this system of congruences:

$$\begin{aligned} z &\equiv c_i \pmod{m_i} \mspace20pt (i = 1, \dotsc, k) \end{aligned}$$

where $\displaystyle c_i = \frac{b_i}{d_i}t_i$ and $\displaystyle m_i = \frac{n_i}{d_i}$.

$\Box$

If you want to show that you are a real nerd, here is an age-guessing game you might play at a party. You ask a fellow party-goer to divide his age by each of the numbers 3, 4, and 5, and tell you the remainders. Show how to use this information to determine his age.

== Attempt ==

Since 3, 4, and 5 are relatively prime, based on the Chinese remainder theorem, we know that the map:

$$\begin{aligned} \tau : I_n &\to I_{n_1} \times \dotsb \times I_{n_k} \\ a &\mapsto (a \bmod n_1, \dotsc, a \bmod n_k) \end{aligned}$$

is a bijection, where

• $\{n_i\}_{i=1}^k$ is a pairwise relatively prime family of integers
• $n := n_1 \dotsm n_k$
• $I_m$ denotes {$0, \dotsc, m-1$} for each positive integer $m$, and
• $a \in \mathbb{Z}$

In other words, with $n := 3 \times 4 \times 5 = 60$ there exists a unique integer $a'$ in $I_{60}$ that would match all the remainders of a given age via dividing $a'$ by each of the numbers 3, 4, and 5. Furthermore, if $a'$ is a solution, $a \equiv a' \pmod {60}$, where $a$ is the final solution.

One way, therefore, is to start by brute forcing $a'$ by trying out all positive integers less than 60. Once we got that, it should be easy to tell if we need to add an extra 60 to the final solution by simple observation of the subject person. The assumption is no one lives beyond the age of 119 :)