Lesson Using the little Fermat's theorem to solve a problem on modular arithmetic

Using the little Fermat's theorem to solve a problem on modular arithmetic

Problem 1

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.

    (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).