31.1 Elementary number-theoretic notions

31.1-1

Prove that if $a > b > 0$ and $c = a + b$, then $c \mod a = b$.

$$ \begin{aligned} c \mod a & = (a + b) \mod a \\ & = (a \mod a) + (b \mod a) \\ & = 0 + b \\ & = b. \end{aligned} $$

31.1-2

Prove that there are infinitely many primes.

$$ \begin{aligned} ((p_1 p_2 \cdots p_k) + 1) \mod p_i & = (p_1 p_2 \cdots p_k) \mod p_i + (1 \mod p_i) \\ & = 0 + 1 \\ & = 1. \end{aligned} $$

if $p_1 p_2 \cdots p_k$ is all prime numbers, then $(p_1 p_2 \cdots p_k) + 1$ is a new prime number.

31.1-3

Prove that if $a \mid b$ and $b \mid c$, then $a \mid c$.

• If $a \mid b$, then $b = a \cdot k_1$.
• If $b \mid c$, then $c = b \cdot k_2 = a \cdot (k_1 \cdot k_2) = a \cdot k_3$, then $a \mid c$.

31.1-4

Prove that if $p$ is prime and $0 < k < p$, then $\gcd(k, p) = 1$.

• If $k \ne 1$, then $k \nmid p$.
• If $k = 1$, then the divisor is $1$.

31.1-5

Prove Corollary 31.5.

For all positive integers $n$, $a$, and $b$, if $n \mid ab$ and $\gcd(a, n) = 1$, then $n \mid b$.

Assume for the purpose of contradiction that $n \mid ab$ and $\gcd(a, n) = 1$, but $n \nmid b$, so $gcd(n, b)=1$, for theorem 31.6, $gcd(n, ab)=1$ which is contradicting our assumption.

31.1-6

Prove that if $p$ is prime and $0 < k < p$, then $p \mid \binom{p}{k}$. Conclude that for all integers $a$ and $b$ and all primes $p$,

$(a + b)^p \equiv a^p + b^p \pmod p$.

$$ \begin{array}{rlll} (a + b) ^ p & \equiv & a^p + \binom{p}{1} a^{p - 1}b^{1} + \cdots + \binom{p}{p - 1} a^{1}b^{p - 1} + b^p & \pmod p \\ & \equiv & a^p + 0 + \cdots + 0 + b^p & \pmod p \\ & \equiv & a^p + b^p & \pmod p \end{array} $$

31.1-7

Prove that if $a$ and $b$ are any positive integers such that $a \mid b$, then

$$(x \mod b) \mod a = x \mod a$$

for any $x$. Prove, under the same assumptions, that

$x \equiv y \pmod b$ implies $x \equiv y \pmod a$

for any integers $x$ and $y$.

Suppose $x = kb + c$, we have

$$(x \mod b) \mod a = c \mod a,$$

and

$$x \mod a = (kb + c) \mod a = (kb \mod a) + (c \mod a) = c \mod a.$$

31.1-8

For any integer $k > 0$, an integer $n$ is a $k$th power if there exists an integer $a$ such that $a^k = n$. Furthermore, $n > 1$ is a nontrivial power if it is a $k$th power for some integer $k > 1$. Show how to determine whether a given $\beta$-bit integer $n$ is a nontrivial power in time polynomial in $\beta$.

Because $2^\beta > n$, we only need to test values of $k$ that satisfy $2 \le k < \beta$, therefore the testing procedure remains $O(\beta)$.

For any nontrivial power $k$, where $2 \le k < \beta$, do a binary search on $a$ that costs

$$O(\log \sqrt n) = O(\log \sqrt{2^\beta}) = O(\frac 1 2\log 2^\beta) = O(\beta).$$

Thus, the total time complexity is

$$O(\beta) \times O(\beta) = O(\beta^2).$$

31.1-9

Prove equations $\text{(31.6)}$–$\text{(31.10)}$.

(Omit!)

31.1-10

Show that the gcd operator is associative. That is, prove that for all integers $a$, $b$, and $c$,

$\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)$.

[The following proof is provided by my friend, Tony Xiao.]

Let $d = \gcd(a, b, c)$, $a = dp$, $b = dq$ and $c = dr$.

Claim $\gcd(a, \gcd(b, c)) = d.$

Let $e = \gcd(b, c)$, thus

$$ \begin{aligned} b = es, \\ c = et. \end{aligned} $$

Since $d \mid b$ and $d \mid c$, thus $d \mid e$.

Let $e = dm$, thus

$$ \begin{aligned} b = (dm)s & = dq, \\ c = (dm)t & = dr. \end{aligned} $$

Suppose $k = \gcd(p, m)$,

$$ \begin{aligned} & k \mid p, k \mid m, \\ \Rightarrow & dk \mid dp, dk \mid dm, \\ \Rightarrow & dk \mid dp, dk \mid (dm)s, dk \mid (dm)t, \\ \Rightarrow & dk \mid a, dk \mid b, dk \mid c. \end{aligned} $$

Since $d = \gcd(a, b, c)$, thus $k = 1$.

$$ \begin{aligned} \gcd(a, \gcd(b, c)) & = \gcd(a, e) \\ & = \gcd(dp, dm) \\ & = d \cdot \gcd(p, m) \\ & = d \cdot k \\ & = d. \end{aligned} $$

By the claim,

$$\gcd(a, \gcd(b, c)) = d = \gcd(\gcd(a, b), c).$$

31.1-11 $\star$

Prove Theorem 31.8.

(Omit!)

31.1-12

Give efficient algorithms for the operations of dividing a $\beta$-bit integer by a shorter integer and of taking the remainder of a $\beta$-bit integer when divided by a shorter integer. Your algorithms should run in time $\Theta(\beta^2)$.

Shift left until the two numbers have the same length, then repeatedly subtract with proper multiplier and shift right.

31.1-13

Give an efficient algorithm to convert a given $\beta$-bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most $\beta$ takes time $M(\beta)$, then we can convert binary to decimal in time $\Theta(M(\beta) \lg\beta)$.

(Omit!)