
How to calculate the
...solution of a congruence with modulo notation from the reciprocal
Hey guys, new to the forum. I have been looking through my notes and I am stuck on an area of my number theory module.
I understand the modulo notation and for example that 14 ≡ 2 mod 12, etc etc.
I have the reciprocals (modulo 15):
1bar = 1
2bar = 8
3bar = No such x, also 5bar, 6bar, 9bar, 10bar, 12bar do not exist
4bar = 4
7bar = 13
8bar = 2
11bar = 11
13bar = 7
14bar = 14
I know this is just the reverse process but if someone could explain to me step by step how these solutions are found that would be great.
Thanks

.
Hence .
So your example demonstrates this fact and notice the reciprocal of can be found through the Euclidean algorithm.


I would do this slightly differently from Soroban. To find the reciprocal of 7 (mod 15) we need, as Soroban said, 7x= 15a+ 1 for some integers x and a. That is the same as the Diophantine equation 7x 15a= 1. Now, 7 divides into 15 twice with remainder 1: 15= 2(7)+ 1 which is the same as (2)(7) (1)15= 1 so that x= 2 is a solution. But we want a number between 0 and 14 so add 15: 152= 13 is between 0 and 15 and is equivalent to 2 (mod 15). As I said, only slightly different from Soroban.

Thanks for the replies! Using HallsofIvy's method, when I apply the method to an actual problem I am having trouble. please state where I am going wrong! Im guessing it's in calculating the reciprocals. Sorry about the poor notation!
x ≡ 3 (mod 4)
x ≡ 4 (mod 5)
x ≡ 2 (mod 7)
is the set of congruences I have to solve.
M = (4x5x7) = 140
M1 = (7x5) = 35
M2 = (4x7) = 28
M3 = (4x5) = 20
Now the reciprocals:
M1bar = 35bar ≡ 3bar (mod 4)
3x = 4a +1
3x  4a =1
4 = 1(3) + 1
(1)(3)  (1)(4) =1
x = 1 is a solution. but we need a solution in between 0 and 2. so add 3,
M1bar = 2
now calculate M2bar = 28bar ≡ 3bar (mod 5)
3x = 5a +1
3x  5a = 1
5 = 1(3) + 2
(1)(3)  (1)(5) = 2
x = 1 is a solution. add 5
M2bar = 4
now calculate M3bar = 20bar ≡ 6bar (mod 7)
6x = 7a +1
6x  7a = 1
7 = 1(6) + 1
(1)(6)  (1)(7) = 1
x = 1 is a solution, but we add 7
M3bar = 6
using the formula
x ≡ a1*M1*M1bar+...+an*Mn*Mnbar (mod M)
I get x = (3*35*2) + (4*28*4) +(2*20*6)
x = 898 ≡ 58 (mod 140).
This answer is incorrect however.
A little bit more help required!
Thanks again