Skip to main content

Exercises 6.6 Exercises

1.

A number such as 11, 111, 1111 is called a repunit. Clearly eleven is a prime repunit. Find two more, say how you found them, and how you confirmed they are prime.

2.

Find the prime numbers less than 100 using the Sieve of Eratosthenes (6.2.2). Make sure you actually draw it! Every math student should do this once, and only once.

3.

Prove Lemma 6.3.6; if a prime \(p\) divides a product \(ab\text{,}\) then \(p\) divides at least one of \(a\) or \(b\text{.}\)

4.

Prove Corollary 6.3.7; if a prime \(p\) divides any finite product of numbers, then \(p\) divides at least one of them.

5.

Assuming that \(\gcd(a,b)=1\text{,}\) \(a\mid c\text{,}\) and \(b\mid c\text{,}\) then \(ab\mid c\) as well, using the FTA. (This was proved earlier without it; see Proposition 2.4.10.)

7.

Prove using the FTA that if \(\gcd(a,b)=d\) then \(\gcd\left(\frac{a}{d},\frac{b}{d}\right)=1\text{.}\)

8.

Assuming \(a=\prod_{i=1}^n p_i^{e_i}\text{,}\) \(b=\prod_{i=1}^n p_i^{f_i}\text{,}\) and \(b \mid a\text{,}\) find a formula to fill in the questions marks and prove it using the Fundamental Theorem of Arithmetic:

\begin{equation*} a/b=\prod_{i=1}^n p_i^{???} \end{equation*}
9.

How would you describe a factorization of a rational number? Do you think you could extend the Fundamental Theorem of Arithmetic to this case? If so, how? If not, why would it not be appropriate?

10.

Show that if \(a\) and \(b\) are positive integers and \(a^3\mid b^2\text{,}\) then \(a\mid b\text{.}\)

11.

Show that if \(p^a\parallel m\) and \(p^b\parallel n\text{,}\) then \(p^{a+b}\parallel mn\text{.}\)

12.

Prove Proposition 3.7.2 using the FTA; if \(\gcd(m,n)=1\) and \(mn\) is a perfect square, then so are \(m\) and \(n\text{.}\)

13.

By hand, find the prime factorizations of 36, 756, and 1001. Use these to find the gcd of each pair of these three numbers.

15.

By hand, find the gcd of \(2^2\cdot 3^5\cdot 7^2\cdot 13\cdot 37\) and \(2^3\cdot 3^4\cdot 11\cdot 31^2\text{.}\)

16.

By any method you like, find the prime factorizations of \(2^{24}-1\) and \(10^8-1\text{,}\) as well as their gcd.

In the next few exercises, recall the definition of least common multiple (or lcm) from Exercise 2.5.9.

18.

Find a formula for the lcm using Theorem 6.3.2 by filling in the question marks:

\begin{equation*} \text{lcm}(a,b)=\prod_{i=1}^n p_i^{???} \end{equation*}
19.

Prove that if \(a,b>0\) then \(\gcd(a,b)\text{lcm}(a,b)=ab\) using the FTA.

Here are a few other interesting results that can be shown using prime factorizations as in Section 6.4.

20.

Is it possible for \(n!\) to end in exactly five zeros?

21.

Find a proof that \(\sqrt{2}\) is irrational, and show exactly where it uses the Fundamental Theorem of Arithmetic (or how it avoids using it). Explain whether or not a similar proof to the one you found would work for showing \(\sqrt{3}\) and \(\sqrt{6}\) are irrational.

22.

Show that \(\log_{10} (5)\) is irrational.

23.

Show that \(3^{2/3}\) is irrational.

24.

How would Theorem 6.3.2 fail if we allowed \(n=1\) to have a prime factorization? What if we allowed \(1\) as a prime number?

25.

Prove that the only solutions of \(x^2\equiv x\) (mod \(p\)) are \(x=[0]\) and \(x=[1]\text{,}\) if \(p\) is a prime. (Refer to Question 4.6.7; this and the next exercise answer Exercise 4.7.19.)

26.

Try to decide for exactly which composite moduli \(n\) the previous question is true. (Refer to the interact in Question 4.6.7; this and the previous exercise answer Exercise 4.7.19.)

27.

Find solutions to \(3x-4\equiv 0\) (mod \(25\)) and (mod \(125\)) using the method in Subsection 6.5.2, starting with modulus five.

28.

Find solutions to \(4x-1\equiv 0\) (mod \(121\)) and (mod \(1331\)) using the method in Subsection 6.5.2, starting with modulus eleven.

30.

Let \(\mathbb{Z}[\sqrt{-5}]\) be the set of all numbers of the form \(a+b\sqrt{-5}\) for \(a,b\in\mathbb{Z}\text{.}\) Find two factorizations of \(N=6\) in this set (known as a ring), for which none of the factors are \(\pm 1\text{,}\) nor for which any two factors differ by a factor of \(\pm 1\text{.}\)