?

Log in

No account? Create an account

Well, not much to report since my last entry - I've spent most of the… - John C. Kirk — LiveJournal

Jan. 14th, 2003

06:17 pm

Previous Entry Share Flag Next Entry

Comments:

[User Picture]
From:overconvergent
Date:January 18th, 2003 10:46 am (UTC)

Re: Which was the question ...

(Link)
The answer here is to use congruences and repeated squaring:

for example, let's calculate 10^10 mod 13.

10^2 == (-3)^2 mod 13 so 10^2 == 9 == -4 mod 13.

So 10^4 == (-4)^2 == 3 mod 13, and 10^8 == 9 == -4 mod 13.

Now 10^10=10^2 * 10^ 8, so 10^10 mod 13 == -4 * -4 == 16 == 3 mod 13.

We combine congruences by thinking of a mod b as b*N+a where N is an integer, so we have (13*N-4)*(13N-4)=13*M+3.

A brief exposition of congruences on the web can be found on Mathworld.
(Reply) (Parent) (Thread)