document.write( "Question 360749: Find the remainder when the sum 4^37 + 6^37 is divided by 25.\r
\n" ); document.write( "\n" ); document.write( "A) 5 B) 10 C) 15 D) 20 E) None \n" ); document.write( "

Algebra.Com's Answer #261547 by Sphinx pinastri(17) $\"\"$ $\"About$

You can put this solution on YOUR website!
First, notice that 6 = 10 - 4 and rewrite the problem as:
\n" ); document.write( "(4^37 + (10 - 4)^37) modulo 25\r
\n" ); document.write( "\n" ); document.write( "Expand the last term using binomial formula:
\n" ); document.write( "(4^37 + 10^37 + ... + 37 x 10 x 4^36 - 4^37) modulo 25\r
\n" ); document.write( "\n" ); document.write( "Notice, that 1st and last terms cancel out and all terms with
\n" ); document.write( "10^2 and higher power are equal 0 modulo 25. So we have:
\n" ); document.write( "(37 x 10 x 4^36) modulo 25\r
\n" ); document.write( "\n" ); document.write( "Let's look at 4^36.
\n" ); document.write( "4^36 = 2^72 = 4 x 1024^7\r
\n" ); document.write( "\n" ); document.write( "1024^7 = (1025 - 1)^7
\n" ); document.write( "(1025 - 1)^7 modulo 25 = -1 modulo 25\r
\n" ); document.write( "\n" ); document.write( "So the problem is reduced to:
\n" ); document.write( "(-37 x 4 x 10) modulo 25 =
\n" ); document.write( " (50 - 37) modulo 25 x 40 modulo 25 =
\n" ); document.write( " 13 x 15 modulo 25 =
\n" ); document.write( " 195 modulo 25 =
\n" ); document.write( " 20 \n" ); document.write( "

\n" );