Prove that for integers $a,\;b,\;\dots$

(1) $(a, b) = 1, \; c | a, \; d | a \implies (c, d) = 1$


Suppose $(c, d) = e > 1$. Then $e | c$ and $c | a$ implies $e | a$; similarly $e | b$ so $(a, b) > 1$, a 
contradiction, and therefore $(c, d) = 1$. $\;\;\;\boxdot$


(2) $(a, b) = (a, c) = 1 \implies (a, bc) = 1$

(3) $(a, b) = 1 \implies (a^n, b^k) = 1 \; \; \forall \; \; n \ge 1, k \ge 1$

(4) $(a, b) = 1 \implies (a + b, a - b) = 1 \; or \; 2$

(5) $(a, b) = 1 \implies (a + b, a^2 - ab + b^2) = 1 \; or \; 3$

(6) $(a, b) = 1, \; d|(a + b) \implies (a, d) = (b, d) = 1$

(7) A rational number $a/b$ with $(a, b) = 1$ is a *reduced fraction*. If the sum of two 
reduced fractions is an integer, say $(a/b) + (c/d) = n$, prove that $|b| = |d|$.

(8) An integer is called *squarefree* if it is not divisible by the square of any prime. Prove that 
for every $n \ge 1$ there exist uniquely determined $a > 0$ and $b > 0$ such that $n=a^2b$, where $b$ is *squarefree*.

...

(11) Prove that $n^4 + 4$ is composite if $n > 1$. 

***Solution***

I first tried cases for the ones-digit. For example $n$ even gives $n^4 + 4$ also even and $n$ ending in 
1, 3, 7 or 9 gives $n^4 + 4$ ending in 5. 
However (particularly because the last case does not resolve in this manner) the right thing to try is 
factoring $n^4 + 4$ in some obvious way: 
Constants 1 and 4 or 2 and 2. 


$n^4 + 4 = (n^2 + a \cdot n + 2) (n^2 + b \cdot n + 2)$


This gives $n^4 + b \cdot n^3 + 2 n^2 + a \cdot n^3 + a \cdot b \cdot n^2 + 2 \cdot a \cdot n + 2 n^2 + 2 \cdot b \cdot n + 4$


$n^4 + 4$ plus stuff that needs to be zero: $(b + a)\cdot n^3 + (4 + a \cdot b)\cdot n^2 + (2 \cdot (a + b))\cdot n$


This means $a = -b$ and $a \cdot b = -4$. Great: $a = 2$ and $b = -2$. 


$n^4 + 4 = (n^2 + 2n + 2)(n^2 - 2n + 2)\;\;\;\;\boxdot$


```python
def pf(n):
    pfn, i = [], 2
    while i * i < n:
        while n%i == 0: pfn.append(i); n = n / i
        i = i + 1
    pfn.append(int(n))
    return pfn

def npf(n): return len(pf(n))

def isprime(n): 
    if npf(n) == 1: return True
    return False

for a in range(3):
    s = a * 10 + 5
    t = s*s*s*s + 4
    if isprime(t): print(str(t) + ' is prime') 
    else: print(str(t) + ' factors are ' + str(pf(t)))
```

    629 factors are [17, 37]
    50629 factors are [197, 257]
    390629 factors are [577, 677]


...

...

(20) Let $d = (826, 1890)$. Use the Euclidean algorithm to compute $d$, then express $d$ as a linear combination of 826 and 1890

Solution

$1890 = 826 \cdot 2 + 238$

$826 = 238 \cdot 3 + 112$

$238 = 112 \cdot 2 + 14$

$112 = 14 \cdot 8 + 0$

$d = 14$

$d = u \cdot 826 + v \cdot 1890$ or equivalently $1 = u \cdot 59 + v \cdot 135$

Taking $u$ positive it can take on values ${ 4, 9, 14, 19, \dots }$.

*--a miracle occurs--*

$(d = 14) = 254 \cdot 826 - 111 \cdot 1890$


```python
254*826-111*1890
```




    14



...


(19) F = 1, 1, 2, 3, 5, 8, ... where $\;a_{n+1} = a_n + a_{n-1}$. Prove $(a_n, \; a_{n+1})\;=\;1$. 


(20)


(21)


(22) Prove (a, b) = (a + b, [a, b]).

Theorem R1: For $a > 1$ and $b > 1$ if $(a, b) = 1$ then 

$ 
\begin{align}
\frac{1}{a} + \frac{1}{b}
\end{align}
$ 
is not an integer. 

Proof: As (2, 2) = 2 one of $a$ or $b$ must be greater than 2. 
Therefore $a + b < ab$ and 

$
\begin{align}
0 < \frac{1}{a} + \frac{1}{b} = \frac{a+b}{ab} < 1
\end{align}
$

$\boxdot$

Now suppose $(a,b) = d$ where $a=\alpha d$, $b = \beta d$ and $(\alpha, \beta) = 1$. 
Consider $(a + b, [a,b])$:

$
\begin{align}
(a + b, [a,b]) = ((\alpha + \beta)d, \frac{ab}{(a,b)}) = 
((\alpha + \beta)d, \frac{\alpha\beta d^2}{d}) = d(\alpha + \beta, \alpha\beta)
\end{align}
$

For any prime factor $p$ of $\beta$ we can write $\beta = pq$ where $p$ does not divide into
$\alpha$. What is $(\alpha + \beta)/(\alpha \beta)$?


$
\begin{align}
\frac{\alpha + \beta}{\alpha \beta} = \frac{1}{\beta} + \frac{1}{\alpha}
\end{align}
$

which is not an integer. 





Left off here: Show (alpha + beta, alpha beta) = 1 by dividing alpha q p into alpha + beta...


(23) Find $a, b > 0 \;\; \ni \;\; a + b = 5264 \; and \; [a, b] = 200,340$. 


...


(30) If $n > 1$ prove 


$
\begin{align}
\sum_{k=1}^{n} \frac{1}{k}
\end{align}
$


is not an integer.


```python

```

d090f990415a2832145d38d536d4d289872262a8
ipynb
Jupyter Notebook
T1_chapter1_exercises.ipynb
robfatland/boojum
4af0adaa01fb0429dd1afa91376c9276fbd224ea
MIT
T1_chapter1_exercises.ipynb
robfatland/boojum
4af0adaa01fb0429dd1afa91376c9276fbd224ea
MIT
T1_chapter1_exercises.ipynb
robfatland/boojum
4af0adaa01fb0429dd1afa91376c9276fbd224ea
MIT
Qwen/Qwen-72B
1. YES
2. YES