Results 1 to 2 of 2

Thread: 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 $\displaystyle n\equiv k(\bmod 40)$ then $\displaystyle n=k+40j$ for some $\displaystyle j$.
    This means, $\displaystyle 2^n = 2^{k+40j} = 2^k \left( 2^{40} \right)^j \equiv 2^k (\bmod 55)$.
    Since $\displaystyle 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 $\displaystyle G=\mathbb{Z}_{33}^{\times}$.
    This group is isomorphic to $\displaystyle \mathbb{Z}_3^{\times} \times \mathbb{Z}_{11}^{\times} \simeq \mathbb{Z}_2 \times \mathbb{Z}_{10}$.
    Therefore, $\displaystyle G$ has exponent $\displaystyle 10$ i.e. it means $\displaystyle x^{10} = 1$.
    Thus, if $\displaystyle \gcd(n,33)=1$ it would mean $\displaystyle n^{10}\equiv 1(\bmod 33)$ so $\displaystyle n^{11}\equiv n(\bmod 33)$.
    Now if $\displaystyle d=\gcd(n,33)\not = 1$ then it means $\displaystyle d= 3,11,33$.
    If $\displaystyle d=33$ there is nothing to prove.
    To complete the proof note that if $\displaystyle n=3,11$ this is true by mods.
    Thus, if $\displaystyle d=3$ for example then $\displaystyle n=3m$ with $\displaystyle m$ relatively prime to $\displaystyle 33$.
    But then $\displaystyle 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: Jul 8th 2011, 06:09 PM
  2. Number Theory
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 19th 2010, 07:51 PM
  3. Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Feb 16th 2010, 05:05 PM
  4. Replies: 2
    Last Post: Dec 18th 2008, 05:28 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum