Results 1 to 2 of 2

Math Help - modulo arithmetic proof

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    3

    modulo arithmetic proof

    Hi Guys,

    I was wondering if anyone can help me with a proof for the following:

    ( (S*R)^2 )(mod n)= [( (S^2)(mod n) )(R^2)](mod n)

    where:
    n = pq, p and q are prime numbers, p and q can be ignored
    S < n
    R some random integer

    thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591
    in general, for ANY integers r,s:

    if we write [k] for k (mod n), [(sr)^2)] = [sr][sr] = [s][r][s][r] = [s]^2[r]^2 = [s^2][r^2].

    this is because if a = r mod n, and b = s mod n,

    then a = r + kn, b = s + tn, so ab = (r + kn)(s + tn) = rs + (ks + rt + ktn)n, that is:

    ab = rs (mod n). this is true whether or not any of the integers involved are between 0 and n or not.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modulo arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 15th 2010, 07:10 AM
  2. Modulo Arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 4th 2009, 11:47 AM
  3. Modulo Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 9th 2009, 03:56 AM
  4. modulo arithmetic proof
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: February 17th 2008, 12:33 PM
  5. Modulo arithmetic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 2nd 2007, 05:16 AM

Search Tags


/mathhelpforum @mathhelpforum