Chapter 1

Let \(a, b, d \in \mathbb{Z}\) with \(d \neq 0 .\) Show that \(a \mid b\) if and only if \(d a \mid d b\).

Let \(n\) be a composite integer. Show that there exists a prime \(p\) dividing \(n,\) with \(p \leq n^{1 / 2}\).

Let \(m\) be a positive integer. Show that for every real number \(x \geq 1\), the number of multiples of \(m\) in the interval \([1, x]\) is \(\lfloor x / m\rfloor ;\) in particular, for every integer \(n \geq 1,\) the number of multiples of \(m\) among \(1, \ldots, n\) is \(\lfloor n / m\rfloor\).

Let \(x \in \mathbb{R}\). Show that \(2\lfloor x\rfloor \leq\lfloor 2 x\rfloor \leq 2\lfloor x\rfloor+1\).

Let \(x \in \mathbb{R}\) and \(n \in \mathbb{Z}\) with \(n>0 .\) Show that \(\lfloor\lfloor x\rfloor / n\rfloor=\lfloor x / n\rfloor ;\) in particular, \(\lfloor\lfloor a / b\rfloor / c\rfloor=\lfloor a / b c\rfloor\) for all positive integers \(a, b, c .\)

Let \(a, b \in \mathbb{Z}\) with \(b<0 .\) Show that \((a \bmod b) \in(b, 0]\).

Let \(I\) be a non-empty set of integers that is closed under addition (i.e., \(a+b \in I\) for all \(a, b \in I)\). Show that \(I\) is an ideal if and only if \(-a \in I\) for all \(a \in I\)

Show that for all integers \(a, b, c,\) we have: (a) \(\operatorname{gcd}(a, b)=\operatorname{gcd}(b, a) ;\) (b) \(\operatorname{gcd}(a, b)=|a| \Longleftrightarrow a \mid b ;\) (c) \(\operatorname{gcd}(a, 0)=\operatorname{gcd}(a, a)=|a|\) and \(\operatorname{gcd}(a, 1)=1 ;\) (d) \(\operatorname{gcd}(c a, c b)=|c| \operatorname{gcd}(a, b)\).

Show that for all integers \(a, b\) with \(d:=\operatorname{gcd}(a, b) \neq 0\), we have \(\operatorname{gcd}(a / d, b / d)=1\)

Let \(n\) be an integer. Show that if \(a, b\) are relatively prime integers, each of which divides \(n,\) then \(a b\) divides \(n\).

Show that two integers are relatively prime if and only if there is no one prime that divides both of them.

Let \(a, b_{1}, \ldots, b_{k}\) be integers. Show that \(\operatorname{gcd}\left(a, b_{1} \cdots b_{k}\right)=1\) if and only if \(\operatorname{gcd}\left(a, b_{i}\right)=1\) for \(i=1, \ldots, k\).

Let \(p\) be a prime and \(k\) an integer, with \(0

An integer \(a\) is called square-free if it is not divisible by the square of any integer greater than \(1 .\) Show that: (a) \(a\) is square-free if and only if \(a=\pm p_{1} \cdots p_{r},\) where the \(p_{i}\) 's are distinct primes; (b) every positive integer \(n\) can be expressed uniquely as \(n=a b^{2},\) where \(a\) and \(b\) are positive integers, and \(a\) is square-free.

For each positive integer \(m,\) let \(I_{m}\) denote \(\\{0, \ldots, m-1\\} .\) Let \(a, b\) be positive integers, and consider the map $$ \begin{aligned} \tau: I_{b} & \times I_{a} \rightarrow I_{a b} \\ (s, t) & \mapsto(a s+b t) \bmod a b \end{aligned} $$ Show \(\tau\) is a bijection if and only if \(\operatorname{gcd}(a, b)=1\).

Let \(a, b, c\) be positive integers satisfying \(\operatorname{gcd}(a, b)=1\) and \(c \geq(a-1)(b-1) .\) Show that there exist non-negative integers \(s, t\) such that \(c=a s+b t\)

For each positive integer \(n,\) let \(D_{n}\) denote the set of positive divisors of \(n\). Let \(n_{1}, n_{2}\) be relatively prime, positive integers. Show that the sets \(D_{n_{1}} \times D_{n_{2}}\) and \(D_{n_{1} n_{2}}\) are in one-to-one correspondence, via the map that sends \(\left(d_{1}, d_{2}\right) \in D_{n_{1}} \times D_{n_{2}}\) to \(d_{1} d_{2}\)

Let \(n\) be an integer. Generalizing Exercise \(1.11,\) show that if \(\left\\{a_{i}\right\\}_{i=1}^{k}\) is a pairwise relatively prime family of integers, where each \(a_{i}\) divides \(n\), then their product \(\prod_{i=1}^{k} a_{i}\) also divides \(n\).

Show that for all integers \(a, b, c,\) we have: $$ \text { (a) } \operatorname{lcm}(a, b)=\operatorname{lcm}(b, a) \text { ; } $$ (b) \(\operatorname{lcm}(a, b)=|a| \Longleftrightarrow b \mid a ;\) (c) \(\operatorname{lcm}(a, a)=\operatorname{lcm}(a, 1)=|a| ;\) (d) \(\operatorname{lcm}(c a, c b)=|c| \operatorname{lcm}(a, b)\).

Show that for all integers \(a, b\), we have: $$ \text { (a) } \operatorname{gcd}(a, b) \cdot \operatorname{lcm}(a, b)=|a b| ; $$ (b) \(\operatorname{gcd}(a, b)=1 \Rightarrow \operatorname{lcm}(a, b)=|a b|\).

Let \(a_{1}, \ldots, a_{k} \in \mathbb{Z}\) with \(k>1\). Show that: $$ \operatorname{gcd}\left(a_{1}, \ldots, a_{k}\right)=\operatorname{gcd}\left(a_{1}, \operatorname{gcd}\left(a_{2}, \ldots, a_{k}\right)\right)=\operatorname{gcd}\left(\operatorname{gcd}\left(a_{1}, \ldots, a_{k-1}\right), a_{k}\right) $$ \(\operatorname{lcm}\left(a_{1}, \ldots, a_{k}\right)=\operatorname{lcm}\left(a_{1}, \operatorname{lcm}\left(a_{2}, \ldots, a_{k}\right)\right)=\operatorname{lcm}\left(\operatorname{lcm}\left(a_{1}, \ldots, a_{k-1}\right), a_{k}\right)\)

Let \(a_{1}, \ldots, a_{k} \in \mathbb{Z}\) with \(d:=\operatorname{gcd}\left(a_{1}, \ldots, a_{k}\right) .\) Show that \(d \mathbb{Z}=\) \(\overline{a_{1} \mathbb{Z}+\cdots+a_{k} \mathbb{Z}} ;\) in particular, there exist integers \(z_{1}, \ldots, z_{k}\) such that \(d=a_{1} z_{1}+\) \(\cdots+a_{k} z_{k}\)

Show that if \(\left\\{a_{i}\right\\}_{i=1}^{k}\) is a pairwise relatively prime family of integers, then \(\operatorname{lcm}\left(a_{1}, \ldots, a_{k}\right)=\left|a_{1} \cdots a_{k}\right|\).

Let \(n\) and \(k\) be positive integers, and suppose \(x \in \mathbb{Q}\) such that \(\overline{x^{k}}=n\) for some \(x \in \mathbb{Q}\). Show that \(x \in \mathbb{Z}\). In other words, \(\sqrt[k]{n}\) is either an integer or is irrational.

Show that \(\operatorname{gcd}(a+b, \operatorname{lcm}(a, b))=\operatorname{gcd}(a, b)\) for all \(a, b \in \mathbb{Z}\).

Show that for every positive integer \(k,\) there exist \(k\) consecutive composite integers. Thus, there are arbitrarily large gaps between primes.

Let \(p\) be a prime. Show that for all \(a, b \in \mathbb{Z},\) we have \(v_{p}(a+b) \geq\) \(\min \left\\{v_{p}(a), v_{p}(b)\right\\},\) and \(v_{p}(a+b)=v_{p}(a)\) if \(v_{p}(a)

For a given prime \(p,\) we may extend the domain of definition of \(v_{p}\) from \(\mathbb{Z}\) to \(\mathbb{Q}:\) for non-zero integers \(a, b,\) let us define \(v_{p}(a / b):=v_{p}(a)-v_{p}(b) .\) Show that: (a) this definition of \(v_{p}(a / b)\) is unambiguous, in the sense that it does not depend on the particular choice of \(a\) and \(b\); (b) for all \(x, y \in \mathbb{Q},\) we have \(v_{p}(x y)=v_{p}(x)+v_{p}(y) ;\) (c) for all \(x, y \in \mathbb{Q},\) we have \(v_{p}(x+y) \geq \min \left\\{v_{p}(x), v_{p}(y)\right\\},\) and \(v_{p}(x+y)=\) \(v_{p}(x)\) if \(v_{p}(x)

Let \(n\) be a positive integer, and let \(2^{k}\) be the highest power of 2 in the set \(S:=\\{1, \ldots, n\\} .\) Show that \(2^{k}\) does not divide any other element in \(S\).

Let \(n \in \mathbb{Z}\) with \(n>1\). Show that \(\sum_{i=1}^{n} 1 / i\) is not an integer.

Let \(n\) be a positive integer, and let \(C_{n}\) denote the number of pairs of integers \((a, b)\) with \(a, b \in\\{1, \ldots, n\\}\) and \(\operatorname{gcd}(a, b)=1,\) and let \(F_{n}\) be the number of distinct rational numbers \(a / b,\) where \(0 \leq a