document.write( "Question 1198925: The number 4^1000 - 1 is divisible by
\n" ); document.write( "a) 4 b) 5 c) 7 d) 13 e) 19 \n" ); document.write( "

Algebra.Com's Answer #832603 by ikleyn(52790) $\"\"$ $\"About$

You can put this solution on YOUR website!
.
\n" ); document.write( "The number 4^1000 - 1 is divisible by
\n" ); document.write( "a) 4 b) 5 c) 7 d) 13 e) 19
\n" ); document.write( "~~~~~~~~~~~~~~~\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

\r\n" );
document.write( "(a)  Regarding (a), it is clear that the remainder of division    by 4 is -1, \r\n" );
document.write( "\r\n" );
document.write( "     which is the same as 3 mod(4);  so,    is not divisible by 4.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "(b)  Regarding (b),   =  is divisible by  = 15;\r\n" );
document.write( "\r\n" );
document.write( "     so,    is divisible by 5.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "(c, d, e)  Regarding (c), (d) and (e), I prepared a table below, which shows the remainders\r\n" );
document.write( "\r\n" );
document.write( "     of division   by 7, 13 and 19 respectively.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "       k       mod(7)       mod(13)          mod(13)\r\n" );
document.write( "   ---------------------------------------------------------------\r\n" );
document.write( "\r\n" );
document.write( "       1	  4	           4	               4\r\n" );
document.write( "       2	  2	           3	              16\r\n" );
document.write( "       3	  1	          12	               7\r\n" );
document.write( "       4	  4	           9	               9\r\n" );
document.write( "       5	  2	          10	              17\r\n" );
document.write( "       6	  1	           1	              11\r\n" );
document.write( "       7	  4	           4	               6\r\n" );
document.write( "       8	  2	           3	               5\r\n" );
document.write( "       9	  1	          12	               1\r\n" );
document.write( "      10	  4	           9	               4\r\n" );
document.write( "			\r\n" );
document.write( "	          3	           6	               9   <<<---===  the length of the period.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "     The table shows that for each of these divisors, 7, 13, 19,  the sequence of remainders \r\n" );
document.write( "     is periodical, as it should be.\r\n" );
document.write( "\r\n" );
document.write( "     Each period (in each column) starts from the very first term of the sequence.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "     For mod(7), the remainder 1 is every 3rd term of the sequence.\r\n" );
document.write( "     Since the index/(the degree) of 1000 is not a multiple of 3,   mod(7) is not 1;\r\n" );
document.write( "     hence,    is not divisible by 7.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "     For mod(13), the remainder 1 is every 6th term of the sequence.\r\n" );
document.write( "     Since the index/(the degree) of 1000 is not a multiple of 6,   mod(13) is not 1;\r\n" );
document.write( "     hence,    is not divisible by 13.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "     For mod(19), the remainder 1 is every 9th term of the sequence.\r\n" );
document.write( "     Since the index/(the degree) of 1000 is not a multiple of 9,   mod(19) is not 1;\r\n" );
document.write( "     hence,    is not divisible by 19.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "ANSWER.    (a)  is not divisible.\r\n" );
document.write( "\r\n" );
document.write( "           (b)  is divisible.\r\n" );
document.write( "\r\n" );
document.write( "           (c)  is not divisible.\r\n" );
document.write( "\r\n" );
document.write( "           (d)  is not divisible.\r\n" );
document.write( "\r\n" );
document.write( "           (e)  is not divisible.\r\n" );
document.write( "

\r
\n" ); document.write( "\n" ); document.write( "Solved.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "

\n" );