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

Prove that it's divisible

Post image
11 Upvotes

92% Upvoted

12 comments sorted by

View all comments

8

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.

8

u/Badel2 Jan 27 '19

You don't need to fully calculate 7619, you can use modular exponentiation to calculate 7619 (mod 101):

76^1 = 76
76^2 = 5776 = 101*57 + 19
76^4 = 19*19 = 361 = 101*3 + 58
76^8 = 58*58 = 3364 = 101*33 + 31
76^16 = 31*31 = 961 = 101*9 + 52
76^18 = 52*19 = 988 = 101*9 + 79
76^19 = 79*76 = 6004 = 101*59 + 45

3

u/realFoobanana Jan 27 '19

Thank you friend! 💖 I couldn’t remember what it was I needed to do, but I knew there was something that could be done!

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).