Results 1 to 3 of 3

Math Help - Pls help me find the least non-negative residue of this problem..

  1. #1
    Newbie
    Joined
    Jul 2012
    From
    QC
    Posts
    1

    Pls help me find the least non-negative residue of this problem..

    How can you find the least non-negative residue of 2^20 modulo 35. If using a calculator, we can easily get 11, however, is there a concrete solution to show this? I don't think Fermat's little theorem is applicable since 35 is not a prime. Can we use Euler's Theorem to solve this?
    Last edited by peejigno; July 4th 2012 at 06:03 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Pls help me find the least non-negative residue of this problem..

    We can't use Fermat's little theorem directly, but we can calculate the residues mod 5 and mod 7. By Fermat's little theorem,

    2^5 \equiv 2 (\mod 5) \Rightarrow 2^{20} \equiv 2^4 \equiv 1 (\mod 5).

    Also, the powers of 2 form the sequence 1,2,4,1,2,4,1,2,4... (mod 7). 20 is congruent to 2 (mod 3) so

    2^{20} \equiv 2^2 \equiv 4 (\mod 7)

    Out of the numbers 1,2,3,...,35, we can easily show that 11 is the only number that is both 1 mod 5 and 4 mod 7. Therefore the answer is 11.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    Re: Pls help me find the least non-negative residue of this problem..

    yes, you can use Euler's theorem. since gcd(2,35) = 1, we have:

    2φ(35) = 1 (mod 35).

    now φ(35) = φ(5)φ(7) = (4)(6) = 24.

    this tells us the order of 2 in U(35) is either 2,3,4,6,8,12 or 24. we can eliminate 2,3 and 4 straightaway.

    now 26 = 64 = 29 (mod 35), so the order of 2 is not 6.

    212 = (29)2 = 841 = 1 (mod 35), so the order of 2 is 12.

    thus: 220 = (212)(28) = 28 = (16)2 = 256 = 11 (mod 35).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. problem in negative negative exponential distribution
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: July 4th 2011, 08:29 AM
  2. Find the residue
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: June 14th 2011, 11:39 PM
  3. Replies: 2
    Last Post: March 26th 2009, 05:30 PM
  4. Replies: 5
    Last Post: March 26th 2009, 03:36 PM
  5. find the least positive residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2008, 06:07 PM

Search Tags


/mathhelpforum @mathhelpforum