Harry scores a mark of 64 out of 85 for mechanics and 69 out of 91 for real analysis. By finding the LCM, state which examination was a better performance for Harry.
The LCM of 85 and 91 is 7735.
The mechanics score is
$$\frac{64}{85} = \frac{5824}{7735}$$
The real analysis score is
$$\frac{69}{91} = \frac{5865}{7735}$$
The better performance was in real analysis.
Hotdogs are sold in packages of ten and buns come in packages of eight. What is the least amount of packages you will need to purchase in order that there are no hotdogs or buns left over?
The minimal number of meals will be a multiple of 8 buns and 10 packages. That is, the LCM of 8 and 10.
We have $[8,10]=2^3 \times 5 = 40$.
That means $\frac{40}{10}=4$ 4 hotdog packages and $\frac{40}{8}=5$ bun packages.
The least number of packages is 9.
Determine the LCM of the following pairs of integers:
(a) [45, 81]
(b) [2000, 2015]
(c) [1000, 1001]
(a) We use the prime decompositions of 45 and 81.
$45 = 3^2 \times 5^1$
$81 = 3^4$
So the LCM $[45,81] = 3^4 \times 5^1 = 405$.
(b) We use the prime decompositions of 2000 and 2015.
$2000 = 2^4 \times 5^3$
$2015 = 5^1 \times 13^1 \times 31^1$
So the LCM $[2000, 2015] = 2^4 \times 5^3 \times 13^1 \times 31^1 = 806000$.
(c) We use the prime decompositions of 1000 and 1001.
$1000 = 2^3 \times 5^3$
$1001 = 7^1 \times 11^1 \times 13^1$
So the LCM $[1000,10001] = 2^3 \times 5^3 \times 7^1 \times 11^1 \times 13^1 = 1001000$.
Prove the following important results:
(a) If a prime $p$ is the sum of two squares then $p$ is of the form $4n + 1$.
(b) A prime of the form $4n + 3$ cannot be written as a sum of two squares.
(a) In Exercise (1.2).2 we showed that the square of an integer is of the form $4m$ or $4m+1$ for some integer $m$.
This means we have four possibilities for the sum of two squares, where $x$ and $y$ are some integer.
The only cases that don't contradict $p$ is prime, are where $p$ is of the form $4n+1$, for some integer $n$.
(b) Let's take some care parsing the statement to be proven.
$$ \text{prime of form }4n+3 \quad \implies \quad \neg(\text{prime is sum of two squares})$$
This is equivalent to
$$ \text{prime is sum of two squares} \quad \implies \quad \neg(\text{prime of form }4n+3)$$
Our task is to show that if a prime $p$ is the sum of two squares then it cannot be of the form $4n+3$.
We have shown in (a) above that a if a prime $p$ is the sum of two squares, then it must be of the form $4m+1$, for some integer $m$.
Let's assume, for the purpose of contradiction, that $4m+1$ can be written as $4n+3$.
$$ 4m + 1 = 4n + 3$$
$$ 4m = 4n + 2 $$
$$ m = n + \frac{1}{2} $$
If $m$ and $n$ are integers, this is not possible, and so $4m+1$ cannot be written as $4n+3$.
We have shown that a prime that is the sum of two squares cannot be written as $4n+3$. This is equivalent to showing a prime of the form $4n + 3$ cannot be written as a sum of two squares.
(i) Prove that the product of three consecutive odd numbers is divisible by 3.
(ii) Prove that $p= 3$ is the only prime such that $p$, $p + 2$, and $p + 4$ are all prime.
(i) For any integer $n$ we can use the Division Algorithm to write it as
$$ n = 3m + r$$
for some integer $m$, and $0 \le r < 3$.
If $n$ is odd, the product of three consecutive odd numbers is
$$ (3m + r)(3m + r + 2)(3m + r + 4) $$
There are 3 cases to consider, $r=0, r=1, r=2$.
In all cases, the product $n(n+2)(n+4)$ is divisible by 3.
So the product of 3 consecutive odd numbers is divisible by 3.
(In fact, the result holds for 3 consecutive even numbers).
(b) Lets split the primes into three cases
Let's consider each case in turn.
The first case, all primes $p>3$, are odd, and we have shown that the product $p(p+2)(p+4)$ is divisible by 3. Since $p$ is not divisible by 3, it must be that one of $(p+2)$ and $(p+4)$ is divisible by 3, and therefore not prime.
For the second case, we only consider the prime $p=3$. Here $p+2=5$ and $p+4=7$, all of which are prime.
For the third case, we only consider the prime $p=2$. Here $p+2=4$ and $p+4=6$, both of which are not prime.
We have shown that 3 is the only prime $p$ such that $p$, $p+2$ and $p+4$ are all prime.
(a) Prove that there are infinitely many primes of the form 3n + 1.
(b) Prove that there are infinitely many primes of the form 3n + 2.
(c) Explain why there are no primes of the form 3n + 3.
(a) The Dirichlet Theorem, noting that 3 and 1 are co-prime, tells us there are infinitely many primes of the form $3n+1$.
(b) The Dirichlet Theorem, noting that 3 and 2 are co-prime, tells us there are infinitely many primes of the form $3n+2$.
(c) Numbers of the form $3n+3 = 3(n+1)$ are divisible by 3 and so are not prime.
(a) Prove there are infinitely many primes of the form $4n + 1$.
(b) Provide another proof that there are infinitely many primes of the form $4n + 3$.
(c) Let $p$ prime such that $p > 3$. Prove that $p$ is of the form $6n + 1$ or $6n + 5$.
Part (c) means that every prime > 3 can be written as $6n + 1$ or $6n + 5$.
(a) We use Dirichlet’s Theorem (2.17):
Let $a$ and $b$ be relatively prime positive integers, then the arithmetic progression
$$a, \; a + b, \; a + 2b, \; a + 3b, \; \ldots$$
contains infinitely many primes.
Numbers of the form $4n +1$ are an arithmetic progression, $1, 1+4, 1+2(4), 1 + 3(4), \ldots$.
Dirichlet's Theorem with $a=1$ and $b=4$, and noting that 4 and 1 are coprime, tells us the sequence contains infinitely many primes.
(b) Dirichlet's Theorem, taking $a=3$ and $b=4$, noting 3 and 4 are coprime, tells us the sequence of numbers of the form $4n+3$ contain infinitely many primes.
(c) We use the Division Algorithm
For $a$ and $b ≥ 1$, there exist $q$ and $r$ such that $a = bq + r$ where $0 ≤ r < b$
So for a prime $p$ such that $p>3$, there exist $n$ and $0 \le r < 6$ such that
$$ p = 6n+ r $$
Let's consider each case of $r$.
This leaves $r=1$ and $r=5$, corresponding to $p=6n+1$ and $p=6n+5$.