###### tags: `MATA02-2022`
# Ungraded problems 5

You are to work on these questions only for the benefit of learning the material. These problems are meant for practice, not an assignment to be handed in.

## 1.
Find 8 consecutive composite integers, that is 8 consecutive integers, of which none is a prime number.

## 2.
Find the prime decomposition of each of the following numbers:
- 104,500
- 83,490
Then find their greatest common divisor and their least common multiple.

## 3.
1. Find the prime factorization of 36,764 and 30,240.
2. Determine the greatest common divisor of 36,764 and 30,240 by using the prime factorization you found in part 1.
3. Determine the greatest common divisor of 36,764 and 30,240 by using the Euclidean algorithm.

## 4.
Consider the numbers $m = 2^8\cdot 3^5 \cdot 7^3$ and $n = 2^5 \cdot 5^4 \cdot 7^2 \cdot 11^3$.
1. How many positive whole numbers divide $m$?
2. How many positive integers divide both $m$ and $n$?

## 5.
Determine if each of the following pairs of numbers are relatively prime.

1. 66 and 70
2. 96 and 150
3. 234 and 399
4. 7 and 43,784
5. 64 and 32,965

## 6.
Find the following

1. $\phi(55)$
2. $\phi(128)$
3. $\phi(99)$
4. $\phi(89)$
5. $\phi(105)$

# Selected (partial) solutions
<details>
<summary>Solutions to selected problems (click to expand)</summary>

## 1.
We can use the prime deserts theorem we showed in class. The following are a set of 8 numbers, none of which are prime:

- $9! + 2 = 362882$
- $9! + 3 = 362883$
- $9! + 4 = 362884$
- $9! + 5 = 362885$
- $9! + 6 = 362886$
- $9! + 7 = 362887$
- $9! + 8 = 362888$
- $9! + 9 = 362889$

## 2.
- $104,500 = 2^2 \cdot 5^3 \cdot 11 \cdot 19$
- $83,490 = 2 \cdot 3 \cdot 5 \cdot 11^2 \cdot 23$
- $\gcd(104500, 83490)=2\cdot 5 \cdot 11 = 110$ (take minimum exponents)
- $\textrm{lcm}(104500, 83490) = 2^2 \cdot 3 \cdot 5^3 \cdot 11^2 \cdot 19 \cdot 23 = 79315500$ (take maximum exponents)

## 3.
- Both methods should give $\gcd(36764, 30240) = 28$

## 4.
- $(8+1)(5+1)(3+1) = 216$ numbers divide $m$
- $(5+1)(4+1)(2+1)(3+1) = 360$ numbers divide $n$
- In order to determine how many numbers divide by $m$ and $n$, we need to find $\gcd(m,n) = 2^5 \cdot 7^2$. Then $(5+1)(2+1) = 18$ numbers divide both.

## 5.
Note that on graded assignments or quizzes or midterms, you may have to show your work.

There are several ways to solve this, all of which involve checking for a common factor. The easiest way is if you recognize both have a common factor, but that may not always be easy. The Euclidean algorithm for finding the gcd will always work, as if the gcd is 1, then they are relatively prime.
1. Not relatively prime (common factor 2)
2. Not relatively prime (common factor 2)
3. Not relatively prime (common factor 3)
4. Relatively prime (no common factor)
5. Relatively prime (no common factor)

## 6.
1. $\phi(55) = 55 \cdot \frac{4}{5} \cdot \frac{10}{11} = 40$
2. $\phi(128) = 128 \cdot \frac{1}{2} = 64$
3. $\phi(99) = 99 \cdot \frac{2}{3} \cdot \frac{10}{11} = 60$
4. $\phi(89) = 89 \cdot \frac{88}{89} = 88$
5. $\phi(105) = 105 \cdot \frac{2}{3} \frac{4}{5} \cdot \frac{6}{7} = 48$

</details>