More divisibility

**shadow_2145** · July 7th 2008, 02:44 PM

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

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

(b) $[a,b] = ab/(a,b)$ if $a>0$ and $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: $10^3 = 999+1$ and similarly for other powers of 10.]

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

Thanks for any help!

**JaneBennet** · July 7th 2008, 07:41 PM

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

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

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

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

2(a) If $N=10^{n}a_n+10^{n-1}a_{n-1}+\ldots+10^0a_0$ , then $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 $N\equiv a_n+a_{n-1}+\ldots+a_0\pmod{3}$ since $10^r-1$ is divisible by 3 for all non-negative integers r.

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

Thread: More divisibility

LinkBack

Thread Tools

Display

More divisibility

Similar Math Help Forum Discussions

Divisibility 11

Divisibility (gcd) 10

Divisibility (gcd) 9

Divisibility (gcd) 8

Divisibility

Search Tags