NTIC Exercises

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. (Bonus: Do the same exercise in a base other than decimal – or unary or binary!)

🔗

2.

Find the prime numbers less than 100 using the Sieve of Eratosthenes (6.2.3). 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 $a b,$ then $p$ divides at least one of $a$ or $b .$

🔗

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,$ $a ∣ c,$ and $b ∣ c,$ then $a b ∣ c$ as well, using the FTA. (This was proved earlier without it; see Proposition 2.4.10.)

🔗

6.

Prove that if $gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ as well, using the FTA. (This was proved earlier without it; see Exercise 2.5.19 and Proposition 2.4.10.)

🔗

7.

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

🔗

8.

Assuming $a = \prod_{i = 1}^{n} p_{i}^{e_{i}},$ $b = \prod_{i = 1}^{n} p_{i}^{f_{i}},$ and $b ∣ a,$ find a formula to fill in the questions marks and prove it using the Fundamental Theorem of Arithmetic:

a / b = \prod_{i = 1}^{n} p_{i}^{? ? ?}

🔗

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} ∣ b^{2},$ then $a ∣ b .$

🔗

11.

Show that if $p^{a} ∥ m$ and $p^{b} ∥ n,$ then $p^{a + b} ∥ m n .$

🔗

12.

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

🔗

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.

🔗

14.

Do the prime factorizations in Example 6.3.5.

🔗

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} .$

🔗

16.

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

🔗

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

🔗

17.

Find the pairwise least common multiples in Exercises 6.6.13–6.6.15.

🔗

18.

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

lcm (a, b) = \prod_{i = 1}^{n} p_{i}^{? ? ?}

🔗

19.

Prove that if $a, b > 0$ then $gcd (a, b) lcm (a, b) = a b$ 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],$ 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 $3 x - 4 \equiv 0$ (mod $25$ ) and (mod $125$ ) using the method in Subsection 6.5.2, starting with modulus five.

🔗

28.

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

🔗

29.

Fill in the details of Example 6.5.2.

🔗

30.

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