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!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用