Re: Modular Exponentiation?

In article <1162580362.106473.200470@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<artlogic@xxxxxxxxx> wrote:
I'm sorry if this is the wrong place to post this, but I wondered if
someone could verify if this statement is true or false:

(X^Y) mod N = (((((X mod N) * X) mod N) * X) mod N) * ... caried out Y
times.

Be aware that you are using "mod" as an operator; in mathematics, this is almost
never the case. That is a common practice of Computer Science. But in
mathematics, "mod" represents a binary relation: we say a = b (mod N)
if and only if N divides a-b.

I will use your convention, though.

So you think of "mod N" as a function that, given an integer, returns
the remainder of dividing that integer by N.

The answer is "yes". This is far more obvious with the mathematical
notion, because


If a=b (mod N) and c=d (mod N), then ac = bd (mod N)

Proof: N|a-b since a=b (mod N). N|c*(a-b) = ac-bc.

Also, N|c-d, and therefore N|b*(c-d) = bc-bd.

Since N divides both ac-bc and bc-bd, then N divides the sum,

N|(ac-bc)+(bc-bd) = ac-bd.

So ac = bd (mod N).

In particular, if a=b (mod N), then a^n = b^n (mod N) for every
integer n.


Now, let t be the remainder of dividing X by N. Then your "X mod N"
means "t". Since X = t (mod N) (prove it), it follows that X^Y=t^Y
(mod N).

And X^Y = X^{Y-1)*t = X^{Y-2}*t^2 = X^{Y-r}*t^{r} (mod N) for any
integer 0<= r <= Y. With this you can prove what you want.

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org

.

Relevant Pages

  • Re: AOLS Stats: 13/01/2006-12/02/2006
    ... this patch should easily do that: ... The second expression, (myrand1/10)%10, divides myrand1 by 10, and then ... remainder, which would be 9. ...
    (alt.os.linux.suse)
  • Re: Order modulo p^n (Number Theory)
    ... order via theorems and was getting know where. ... After that I used Newtons binomial and showed that p^n divides all the ... powers less than n-1 the expansion dosent give the remainder 1 and the ... what am I missing here? ...
    (sci.math)
  • Re: prime number routine
    ... > need a routine for figuring out if a number inputted by the user is a prime ... and the number itself which divides that number evenly. ... it is very clear, that if such a potential divisor exists, it cannot be ... In no case were we left with a remainder of 0, ...
    (comp.lang.cpp)
  • Re: Proof of the riemann hypothesis via Meijer-G functions, hypergeometric functions, and Browni
    ... a paper in mathematics. ... Attacking the Riemann Hypothesis as your first ... Find the smallest positive integer n such that ... If g divides ab, cd, and ac + bd, ...
    (sci.math)
  • Re: noob question: easiest way to parse an int?
    ... remainder of 930, i would have the "2nd" digit. ... divides by 10 although converting to string is not a horrible choice. ...
    (comp.lang.java.programmer)