Results 1 to 2 of 2

Math Help - Number Theory

  1. #1
    Junior Member
    Joined
    Apr 2008
    From
    Gainesville
    Posts
    68

    Number Theory

    a) Suppose that n and k are positive integers with n congruent to k mod 40.
    prove that 2^n is congruent to 2^k mod 55.

    b) Prove that for any integer, n

    n^11 is congruent to n mod 33.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by JCIR View Post
    a) Suppose that n and k are positive integers with n congruent to k mod 40.
    prove that 2^n is congruent to 2^k mod 55.
    If n\equiv k(\bmod 40) then n=k+40j for some j.
    This means, 2^n = 2^{k+40j} = 2^k \left( 2^{40} \right)^j \equiv 2^k (\bmod 55).
    Since 2^{40}\equiv 1(\bmod 55) by Euler's theorem.

    b) Prove that for any integer, n

    n^11 is congruent to n mod 33.
    Consider the group G=\mathbb{Z}_{33}^{\times}.
    This group is isomorphic to \mathbb{Z}_3^{\times} \times \mathbb{Z}_{11}^{\times} \simeq \mathbb{Z}_2 \times \mathbb{Z}_{10}.
    Therefore, G has exponent 10 i.e. it means x^{10} = 1.
    Thus, if \gcd(n,33)=1 it would mean n^{10}\equiv 1(\bmod 33) so n^{11}\equiv n(\bmod 33).
    Now if d=\gcd(n,33)\not = 1 then it means d= 3,11,33.
    If d=33 there is nothing to prove.
    To complete the proof note that if n=3,11 this is true by mods.
    Thus, if d=3 for example then n=3m with m relatively prime to 33.
    But then n^{11} = 3^{11} m^{11} \equiv 3m = n(\bmod 33).
    And with that this completes the proof.
    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