Results 1 to 5 of 5

Math Help - Using Congruences - Wilson's and Fermat's Thms

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    District of Columbia
    Posts
    16

    Using Congruences - Wilson's and Fermat's Thms

    This seems like a relatively simple computational problem (in fact I know how to do it for 2^91 divided by 7) but I am not sure how to apply the same process here.

    My question: What is the remainder when 314^162 is divided by 7? (using congruences)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member MaxJasper's Avatar
    Joined
    Aug 2012
    From
    Canada
    Posts
    482
    Thanks
    54

    Lightbulb Re: Using Congruences - Wilson's and Fermat's Thms

    314^{162}\equiv 314^{3*54}\equiv 2^{3*54}*157^{3*54}\equiv N*2^3\equiv N*8

    N*8\equiv 1 \bmod 7
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2012
    From
    District of Columbia
    Posts
    16

    Re: Using Congruences - Wilson's and Fermat's Thms

    So N = 157^54. Why can you substitute N in to the congruence and just consider 8 (mod 7)?
    Last edited by ncshields; October 14th 2012 at 10:06 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member MaxJasper's Avatar
    Joined
    Aug 2012
    From
    Canada
    Posts
    482
    Thanks
    54

    Re: Using Congruences - Wilson's and Fermat's Thms

    It is irrelevant what N is in value...it becomes just a multiplier to the congruent remainder resulting in the same remainder.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2012
    From
    India
    Posts
    61
    Thanks
    3

    Re: Using Congruences - Wilson's and Fermat's Thms

    I will explain a bit. I think he did not get the direct steps, and skipping. For all these questions, you take the bases modulo first. In case of 2^91 or something, you first raise it to sufficient power that you can take a different modulus than 2, namely, you raise to power 3, it becomes 2 * (2^3)^30 = 2 * 8^30. Since now, 8's modulo is 1 w.r.t 7, then we have, 2 * 8^30 = 2 * 1^30 = 2 (mod 7). Similarly, with 314^162, first take remainder of 314 w.r.t 7, which gives 6 or -1. If you raise this remainder to 162, which is an even number, that will give 1 as the remainder.

    Salahuddin
    Maths online
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: June 12th 2012, 06:30 AM
  2. Fermat, Congruences, the CRT, and an exam question
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 24th 2011, 08:17 PM
  3. Applying Fermat and Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 21st 2010, 06:06 PM
  4. Two problems with Fermat and Wilson
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 5th 2009, 02:48 PM
  5. More on Wilson and Fermat
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 23rd 2008, 07:07 PM

Search Tags


/mathhelpforum @mathhelpforum