MAML, Number Theory: Modular Arithmetic
This is a MAML (Maine Association of Math Leagues) problem from October 2011 (Meet 1 of 2011-12), Round 4, Problem 3: http://maml.net/problems.htm
Also, this was recorded with gtk-recordMyDesktop: http://recordmydesktop.sourceforge.ne...
The math writings were made on Emacs: https://www.gnu.org/software/emacs/
The Khan Academy modular arithmetic tutorial is here: https://www.khanacademy.org/computing...
Turn on captions to understand the audio better.
Share this YouTube channel with the following link! https://bit.ly/nhmyoutubechannel
Condensed Writing Solution:
We must calculate the following:
23^15*47^17 modulo 5
By replacing 23 with 3 (23 is congruent to 3 modulo 5) and 47 with 2 (47 is congruent to 2 modulo 5) and splitting the modulos up over multiplication, we get the following:
3^15*2^17 modulo 5
(3^15 modulo 5)*(2^17 modulo 5)
(3 modulo 5)*(3^2 modulo 5)*(3^4 modulo 5)*(3^8 modulo 5)*(2 modulo 5)*(2^16 modulo 5)
3 modulo 5 is simply 3.
3^2 modulo 5 is 9 modulo 5 which is simply 4.
3^4 (3^2)^2 which is congruent to 4^2=16 modulo 5 which is congruent to 1 modulo 5.
Similarly, 3^8 is (3^4)^2 which is congruent to 1^2=1 modulo 5.
2 modulo 5 is simply 2.
2^16 is (2^8)^2 or 256^2 which is congruent to 1^2=1 modulo 5.
Thus, the above expression is equal to:
3*4*1*1*2*1 modulo 5
24 modulo 5
4 ANSWER