document.write( "Question 1207682: For a certain positive integer $n$, the number $n^{6873}$ leaves a remainder of $3$ when divided by $131.$ What remainder does $n$ leave when divided by $131$? \n" ); document.write( "
Algebra.Com's Answer #845689 by ikleyn(52780)\"\" \"About 
You can put this solution on YOUR website!
.
\n" ); document.write( "For a certain positive integer $n$, the number $n^{6873}$ leaves a remainder of
\n" ); document.write( "$3$ when divided by $131.$ What remainder does $n$ leave when divided by $131$?
\n" ); document.write( "~~~~~~~~~~~~~~~~~~~~~~~~~~\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "        After seeing the post by @math_tutor, I found some errors in my previous version\r
\n" ); document.write( "\n" ); document.write( "        that should be fixed. I fixed them, and now you see my updated version.\r
\n" ); document.write( "\n" ); document.write( "        Now there is no difference between our final numbers/answers.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "
\r\n" );
document.write( "We are given that the remainder\r\n" );
document.write( "\r\n" );
document.write( "    \"n%5E6873\" mod 131  is 3.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Notice that 131 is a prime number and 6873 = 113 mod 130.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "    Now apply the little Fermat's theorem.\r\n" );
document.write( "\r\n" );
document.write( "    It says that for fixed integer \"n\", where n is relatively prime to 131,  the sequence  \r\n" );
document.write( "    k --> \"n%5Ek\" mod 131 is periodical (= cyclic) over integer values k = 1, 2, 3, . . . \r\n" );
document.write( "     with the period of 130.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "It tells us that \"n%5E6873\" = \"n%5E113\" = 3 mod 131.  \r\n" );
document.write( "Based on this information, we should find {n mod 131}.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "    Let me repeat it again:\r\n" );
document.write( "\r\n" );
document.write( "        Using the little Fermat's theorem, we deduced \r\n" );
document.write( "        from the given info that  \"n%5E113\" = 3 mod 131.\r\n" );
document.write( "        Having it, we want to find  {n mod 131}.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Take  \"n%5E113\" = 3 mod 131 and square it. You will get  \"n%5E%282%2A113%29\" = \"3%5E2\" mod 131.\r\n" );
document.write( "\r\n" );
document.write( "Take  \"n%5E113\" = 3 mod 131 and cube   it. You will get  \"n%5E%283%2A113%29\" = \"3%5E3\" mod 131.\r\n" );
document.write( "\r\n" );
document.write( ". . . and so on . . . \r\n" );
document.write( "\r\n" );
document.write( "Take  \"n%5E113\" = 3 mod 131 and raise to degree m. You will get  \"n%5E%28m%2A113%29\" = \"3%5Em\" mod 131.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "The idea is to find a degree m such that m*113 = 1 mod 130.\r\n" );
document.write( "\r\n" );
document.write( "Then, due to little Fermat's theorem (again) we will have n = \"3%5Em\" mod 131 and will solve our problem this way.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "    Thus, our task is to find m, which is \r\n" );
document.write( "    the Modular Multiplicative Inverse to 113 modulo 130.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Fortunately, in the Internet there are calculators for it,\r\n" );
document.write( "that solve this intermediate task.  See these links\r\n" );
document.write( "\r\n" );
document.write( "    Modular Multiplicative Inverse Calculator\r\n" );
document.write( "    https://planetcalc.com/3311/\r\n" );
document.write( "\r\n" );
document.write( "    Inverse Modulo Calculator\r\n" );
document.write( "    https://www.omnicalculator.com/math/inverse-modulo\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "The Modular Multiplicative Inverse to 113 modulo 130 is 107 modulo 130.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Now the only thing to complete the solution is to find \"3%5E107\" mod 131.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "For it, I created Excel spreadsheet below.\r\n" );
document.write( "\r\n" );
document.write( "The working formula in my spreadsheet is  \"a%5Bn%2B1%5D\" = \"Mod%283%2Aa%5Bn%5D%2C+131%29\",  \"a%5B1%5D\" = 3.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "  T  A  B  L  E \r\n" );
document.write( "\r\n" );
document.write( "k               \"3%5Ek\" mod 131\r\n" );
document.write( "------------------------------------\r\n" );
document.write( "1		  3\r\n" );
document.write( "2		  9\r\n" );
document.write( "3		 27\r\n" );
document.write( "4		 81\r\n" );
document.write( "5		112\r\n" );
document.write( "6		 74\r\n" );
document.write( "7		 91\r\n" );
document.write( "8		 11\r\n" );
document.write( "9		 33\r\n" );
document.write( "10		 99\r\n" );
document.write( "11		 35\r\n" );
document.write( "12		105\r\n" );
document.write( "13		 53\r\n" );
document.write( "14		 28\r\n" );
document.write( "15		 84\r\n" );
document.write( "16		121\r\n" );
document.write( "17		101\r\n" );
document.write( "18		 41\r\n" );
document.write( "19		123\r\n" );
document.write( "20		107\r\n" );
document.write( "21		 59\r\n" );
document.write( "22		 46\r\n" );
document.write( "23		  7\r\n" );
document.write( "24		 21\r\n" );
document.write( "25		 63\r\n" );
document.write( "26		 58\r\n" );
document.write( "27		 43\r\n" );
document.write( "28		129\r\n" );
document.write( "29		125\r\n" );
document.write( "30		113\r\n" );
document.write( "31		 77\r\n" );
document.write( "32		100\r\n" );
document.write( "33		 38\r\n" );
document.write( "34		114\r\n" );
document.write( "35		 80\r\n" );
document.write( "36		109\r\n" );
document.write( "37		 65\r\n" );
document.write( "38		 64\r\n" );
document.write( "39		 61\r\n" );
document.write( "40		 52\r\n" );
document.write( "41		 25\r\n" );
document.write( "42		 75\r\n" );
document.write( "43		 94\r\n" );
document.write( "44		 20\r\n" );
document.write( "45		 60\r\n" );
document.write( "46		 49\r\n" );
document.write( "47		 16\r\n" );
document.write( "48		 48\r\n" );
document.write( "49		 13\r\n" );
document.write( "50		 39\r\n" );
document.write( "51		117\r\n" );
document.write( "52		 89\r\n" );
document.write( "53		  5\r\n" );
document.write( "54		 15\r\n" );
document.write( "55		 45\r\n" );
document.write( "56		  4\r\n" );
document.write( "57		 12\r\n" );
document.write( "58		 36\r\n" );
document.write( "59		108\r\n" );
document.write( "60		 62\r\n" );
document.write( "61		 55\r\n" );
document.write( "62		 34\r\n" );
document.write( "63		102\r\n" );
document.write( "64		 44\r\n" );
document.write( "65		  1\r\n" );
document.write( "66		  3\r\n" );
document.write( "67		  9\r\n" );
document.write( "68		 27\r\n" );
document.write( "69		 81\r\n" );
document.write( "70		112\r\n" );
document.write( "71		 74\r\n" );
document.write( "72		 91\r\n" );
document.write( "73		 11\r\n" );
document.write( "74		 33\r\n" );
document.write( "75		 99\r\n" );
document.write( "76		 35\r\n" );
document.write( "77		105\r\n" );
document.write( "78		 53\r\n" );
document.write( "79		 28\r\n" );
document.write( "80		 84\r\n" );
document.write( "81		121\r\n" );
document.write( "82		101\r\n" );
document.write( "83		 41\r\n" );
document.write( "84		123\r\n" );
document.write( "85		107\r\n" );
document.write( "86		 59\r\n" );
document.write( "87		 46\r\n" );
document.write( "88		  7\r\n" );
document.write( "89		 21\r\n" );
document.write( "90		 63\r\n" );
document.write( "91		 58\r\n" );
document.write( "92		 43\r\n" );
document.write( "93		129\r\n" );
document.write( "94		125\r\n" );
document.write( "95		113\r\n" );
document.write( "96		 77\r\n" );
document.write( "97		100\r\n" );
document.write( "98		 38\r\n" );
document.write( "99		114\r\n" );
document.write( "100		 80\r\n" );
document.write( "101		109\r\n" );
document.write( "102		 65\r\n" );
document.write( "103		 64\r\n" );
document.write( "104		 61\r\n" );
document.write( "105		 52\r\n" );
document.write( "106		 25\r\n" );
document.write( "107		 75    <---=== \r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "The ANSWER to the problem's question is 75.\r\n" );
document.write( "\r\n" );
document.write( "In other words, n leaves the remainder 75 when is divided by 131.\r\n" );
document.write( "
\r
\n" ); document.write( "\n" ); document.write( "Solved.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "------------------\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Couple of post-solution notes:\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "
\r\n" );
document.write( "    (1)  Finding the Modular Multiplicative Inverse to 61 modulo 131 is a technical issue.\r\n" );
document.write( "\r\n" );
document.write( "         I used and referred to online calculators with the only goal do not distract \r\n" );
document.write( "         a reader from the mainstream idea of the solution.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "    (2)  The method making calculations in the spreadsheet is to avoid overflowing (= loosing the precision)\r\n" );
document.write( "         when using direct formula for  (\"3%5Em\" mod 131).\r\n" );
document.write( "
\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "
\n" );