Results 1 to 2 of 2

Math Help - More divisibility

  1. #1
    Member
    Joined
    Mar 2008
    Posts
    99

    More divisibility

    (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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    (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
    Last edited by JaneBennet; July 7th 2008 at 08:05 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum