?
LiveJournal
Find more
Communities
RSS Reader
Shop
Help
Login
Login
CREATE BLOG
Join
English
(en)
English (en)
Русский (ru)
Українська (uk)
Français (fr)
Português (pt)
español (es)
Deutsch (de)
Italiano (it)
Беларуская (be)
johnckirk
—
Subscribe
Readability
Log in
No account?
Create an account
Remember me
Forgot password
Log in
Log in
Facebook
Twitter
Google
Well, not much to report since my last entry  I've spent most of the…  John C. Kirk — LiveJournal
(
Recent Entries
)
(
Archive
)
(
Friends
)
(
Profile
)
(
My Website
)
Jan. 14th, 2003
06:17 pm
(
3 comments

Leave a comment
)
Comments:
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*N4)*(13N4)=13*M+3.
A brief exposition of congruences on the web can be found on
Mathworld
.
(
Reply
) (
Parent
) (
Thread
)
Re: Which was the question ...
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*N4)*(13N4)=13*M+3.
A brief exposition of congruences on the web can be found on Mathworld.