Results 1 to 2 of 2

Math Help - Two problems with Fermat and Wilson

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    Two problems with Fermat and Wilson

    Prove that if r_{1}, r_{2},..., r_{\Phi (m)} is a reduced residue system modulo m, and m is odd, then  r_{1} + r_{2} + ... + r_{\phi (m)} \equiv 0. (mod m).

    and

    What is the remainder when 473^{38} is divided by 5?

    Any help would be appreciated! Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by kyldn6 View Post
    Prove that if r_{1}, r_{2},..., r_{\Phi (m)} is a reduced residue system modulo m, and m is odd, then  r_{1} + r_{2} + ... + r_{\phi (m)} \equiv 0. (mod m).

    and

    What is the remainder when 473^{38} is divided by 5?

    Any help would be appreciated! Thanks!

    First let us write r_1,..., r_s for the Reduced Residue System (RRS), for simplicity, with s = Phi(m).

    Asumme m > 2 so that phi(m) > 1, and let r be any of the elements in the
    RRS DIFFERENT from 1, and put S = r_1 +...+ r_s, so:

    r*S = r(r_1 +...+ r_s) = r*r_1 +...+ r*r_s = S , since for any 1 <= i <=

    there exists 1 <= j <= s s.t. r*r_i = r_j (the RRS is closed under multiplication).

    Thuis, we got rS = S ==> S = 0 since r is not 1.

    as for 473^38 mod 5: the powers of integers ending in 3 have a period 4, and the last digit in each power is 3,9,7,1,3,9,7,1,...etc.

    So all we must know is 38 = 2 (mod 4) ==> 473^38 ends with 9 ==> 473^38 equals 4 mod 5 (or if you want: the remainder of 473^38 when divided by 5 is 4)

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermat Numbers Problems
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: May 14th 2010, 11:34 AM
  2. Problem (Wilson's)
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 5th 2010, 02:51 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. Wilson theorem
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: May 16th 2009, 02:30 AM
  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