1. ## More divisibility

(1) The least common multiple of nonzero integers $\displaystyle a$ and $\displaystyle b$ is the smallest positive integer $\displaystyle m$ such that $\displaystyle a|m$ and $\displaystyle b|m$ ; $\displaystyle m$ is usually denoted $\displaystyle [a,b]$. Prove that:

(a) whenever $\displaystyle a|k$ and $\displaystyle b|k$, then $\displaystyle [a,b]|k$

(b) $\displaystyle [a,b] = ab/(a,b)$ if $\displaystyle a>0$ and $\displaystyle b>0$

(2) Prove that a positive integer is divisible by 3 if and only if the sum of its digits is divisible by 3. [Hint: $\displaystyle 10^3 = 999+1$ and similarly for other powers of 10.]

(3) Prove that for every $\displaystyle n, (n+1, n^2-n+1)$is $\displaystyle 1 or 3$

Thanks for any help!

2. (a) Write $\displaystyle k=q\cdot[a,b]+r$ where $\displaystyle 0\leq r<[a,b]$.

Since a divides both k and $\displaystyle [a,b]$, a divides r. Similarly b divides r because it divides both k and $\displaystyle [a,b]$.

So $\displaystyle a\mid r$ and $\displaystyle b\mid r$. As $\displaystyle [a,b]$ is the least positive integer divisible by both a and b and $\displaystyle r<[a,b]$, r cannot be positive. $\displaystyle \therefore\ r=0$, i.e. $\displaystyle [a,b]\mid k$.

(b) First show that if $\displaystyle \gcd(a,b)=1$, then $\displaystyle [a,b] = ab$. Then note that for any positive integer k, $\displaystyle \gcd(ka,kb)=k\gcd(ka,kb)$ and $\displaystyle [ka,kb] = k[a,b]$.

2(a) If $\displaystyle N=10^{n}a_n+10^{n-1}a_{n-1}+\ldots+10^0a_0$, then $\displaystyle a_n+a_{n-1}+\ldots+a_0=N-\left[(10^{n}-1)a_n+(10^{n-1}-1)a_{n-1}+\ldots+(10^0-1)a_0\right]$. Hence $\displaystyle N\equiv a_n+a_{n-1}+\ldots+a_0\pmod{3}$ since $\displaystyle 10^r-1$ is divisible by 3 for all non-negative integers r.

(b) $\displaystyle n^2-n+1=(n-2)(n+1)+3$