Results 1 to 6 of 6

Math Help - number theory

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    12

    Thumbs up number theory

    1.find last two digits of 2^1000
    2.(a,a+k)/k for a,knot equel to 0
    3.(a,b)=1 and c>0 prove that an integer sugh that (a+bx,c)=1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1
    Quote Originally Posted by vinodannu View Post
    1.find last two digits of 2^1000
    2.(a,a+k)/k for a,knot equel to 0
    3.(a,b)=1 and c>0 prove that an integer sugh that (a+bx,c)=1
    I'll leave all of this to the experts, but 2 and 3 are not written clearly. I don't know what 2) is asking for at all, and for 3) if we set x = 0 and c = b then we have found such an x. It seems too trivial.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    From
    Melbourne Australia
    Posts
    216
    Thanks
    29

    Q1

    Start writing down the last two digits of the sequence of numbers 2^1,2^2,2^3 .

    You will find that after every 20 entries the last two digits start to repeat. This is not surprising because the last two digits of 16*2^{20} are 16.

    Now you don't have to go all of the way up to 1000 because there is a clear pattern.

    If we seek 2^n then:

    if n = 20X+1 then the last two digits are 52 (X>1)

    For example the last digit of 2^{441} is 52.

    You can find the last two digits of 2^{1000} in a similar way.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Quote Originally Posted by vinodannu View Post
    1.find last two digits of 2^1000
    Note that 2^{20}=1048576\equiv76\pmod{100}

    Now 76 is a good number to play with here because the last two digits of any of its positive powers are 76 (e.g. 76^2=5776, 76^3=438976, etc).

    Hence 2^{1000}=\left(2^{20}\right)^{50}\equiv76^{50}\pmo  d{100}\equiv76\pmod{100}.

    So the last two digits of 2^{1000} are 76.

    Quote Originally Posted by vinodannu View Post
    2.(a,a+k)/k for a,knot equel to 0
    Let d=\gcd(a,a+k). Then d\mid a and d\mid a+k.

    \therefore d\mid(a+k)-a=k
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Quote Originally Posted by vinodannu View Post
    3.(a,b)=1 and c>0 prove that an integer sugh that (a+bx,c)=1
    All right, this one is tricky, but I think we can prove the contrapositive statement instead: If \gcd(a+bx,c)>1 for all integers x, then \gcd(a,b)>1.

    Let \gcd(a+bx,c)=d>1. Then d\mid a+bx for all x\in\mathbb{Z}. In particular, d\mid a=a+b\cdot0. Hence, by the result in part 2, d\mid bx for all x\in\mathbb{Z}; in particular, d\mid b=b\cdot1.

    So d\mid a and d\mid b. \therefore\ \gcd(a,b)\ge d>1.
    Last edited by JaneBennet; August 10th 2008 at 02:55 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by JaneBennet View Post

    Let \gcd(a+bx,c)=d>1. Then d\mid a+bx for all x\in\mathbb{Z}.
    this is not true because d and x are dependent. the problem is strangely tricky! here's my proof which is constructive: we'll consider two cases:

    Case 1 every prime divisor of c divides a: let x=1 and suppose p is a prime divisor of c. if p | a+b, then p|b, which is impossible because then p|\gcd(a,b)=1. thus \gcd(a+b,c)=1.

    Case 2 some prime divisors of c do not divide a: let x be the product of all prime divisors of c that do not divide a. now let p be a prime divisor of c and suppose that p|a+bx. \ \ \ (1)

    subcase1: if p|a, then by (1): p|bx. then since \gcd(a,b)=1, we must have p|x, which is impossible by the definition of x.

    subcase 2: if p does not divide a, then by the definition of x we'll have p|x and thus by (1): p|a, which is a contradiction! thus \gcd(a+bx,c)=1. \ \ \ \square
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 07:09 PM
  2. Number Theory
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 19th 2010, 08:51 PM
  3. Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: February 16th 2010, 06:05 PM
  4. Replies: 2
    Last Post: December 18th 2008, 06:28 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 09:11 PM

Search Tags


/mathhelpforum @mathhelpforum