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.

🔗

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 primes, 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.9.)

🔗

6.

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

🔗

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.

🔗

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\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.

🔗

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:

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

🔗

29.

Fill in the details of Example 6.5.2.

🔗

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