91Ó°ÊÓ

Prove that \(\operatorname{gcd}(n, n+1)=1\) for any \(n \in \mathrm{N} .\) Find integers \(x\) and \(y\) such that \(n x+(n+1) y=1\)

Let \(A\) be the set of congruence classes of integers modulo some natural number \(n .\) For \(\bar{a}, \bar{b} \in A\), define \(\bar{a} \preceq \bar{b}\) if \(a b \equiv a^{2}(\bmod n) .\) Prove or disprove that \(\preceq\) is a partial order in each of the following cases. (a) \(n=p\) is a prime. (b) \(n=p q\) is the product of two distinct primes. (c) \(n\) is divisible by the square of a prime. [Hint: It might be helpful first to consider the case \(n=12.1\)

True or false: \(\left\\{n \in \mathrm{N} \mid n>2\right.\) and \(a^{n}+b^{n}=\) \(c^{n}\) for some \(\left.a, b, c \in N\right\\}=\emptyset ?\)

Suppose that \(a, b\), and \(c\) are integers each two of which are relatively prime. Prove that \(\operatorname{gcd}(a b, b c, a c)=1\)

Let \(n\) and \(s\) be positive integers and suppose \(k\) is the least positive integer such that \(n \mid k s\). Prove that \(k=\) \(\frac{n}{\operatorname{gcd}(n, s)}\)

Let \(a, b\), and \(c\) be integers each relatively prime to another integer \(n\). Prove that the product \(a b c\) is relatively prime to \(n\).

Find \(\operatorname{lcm}(63,273)\) and \(\mathrm{lcm}(56,200) .\) [Hint \(:\) An easy method takes advantage of formula (2) of this section.]

Given that \(p\) is prime, \(\operatorname{gcd}\left(a, p^{2}\right)=p\) and \(\operatorname{gcd}\left(b, p^{3}\right)=\) \(p^{2}\), find (a) \([\mathrm{BB}] \operatorname{gcd}\left(a b, p^{4}\right)\) (b) \(\operatorname{gcd}\left(a+b, p^{4}\right)\)

Let \(p_{1}, p_{2}, \ldots, p_{n+1}\) denote the first \(n+1\) primes (in order). Prove that every number between \(p_{1} p_{2} \cdots p_{n}+2\) and \(p_{1} p_{2} \cdots p_{n}+p_{n+1}-1\) (inclusive) is composite. How does this show that there are gaps of arbitrary length in the sequence of primes?

Let \(a\) and \(b\) be nonzero integers with \(\operatorname{lcm}(a, b)=\ell\). Let \(m\) be any common multiple of \(a\) and \(b\). Prove that \(\ell \mid m\).