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