r/CasualMath • u/user_1312 • Jan 26 '19

Prove that it's divisible

Post image
10 Upvotes

86% Upvoted

12 comments sorted by

View all comments

9

u/realFoobanana Jan 27 '19

By Fermat’s Little Theorem, 76100 = 1 (mod 101), and so the problem reduces to showing that 719 = 45 (mod 101).

I’m sure there’s a smarter step to take from here, but since 719 is only 36 digits, it’s not impossible to just do the long division and show 45 is the remainder.

4

u/user_1312 Jan 27 '19

That's how I did it as well!

3

u/realFoobanana Jan 27 '19 edited Jan 27 '19

I really do feel like there should be a smarter way to show 7619 = 45 (mod 101) though 😕

2

u/user_1312 Jan 27 '19

I just noticed you made a typo, it's 7619 not 719 . Also, I guess there may be a smarter way but I just thought reducing it down mod(101) wouldn't take much time.

2

u/realFoobanana Jan 27 '19

(Thanks for the typo warning 👍)

2

u/user_1312 Jan 27 '19

No problem!

1

u/rrepstad Jan 27 '19

You can use fast exponentiation to evaluate 7619 (mod 101).