...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.
Dec 30th 2009, 03:27 PM
So your example demonstrates this fact and notice the reciprocal of can be found through the Euclidean algorithm.
Dec 30th 2009, 06:39 PM
Hello, Hamster Jam!
Here's a primitive (but very simple) approach . . .
Finding reciprocals in modulo notation.
I have the reciprocals (mod 15):
No reciprocals for 3, 5, 6, 9, 10, or 12.
If someone could explain to me step by step
how these solutions are found, that would be great.
Let's find the reciprocal of 7.
We want a number such that: .
That is: . for some integer
Since is an integer, must be a multiple of 7.
The first time this happens is: .
. . Therefore, the reciprocal of 7 is 13 (in mod 15).
Dec 31st 2009, 05:16 AM
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: 15-2= 13 is between 0 and 15 and is equivalent to -2 (mod 15). As I said, only slightly different from Soroban.
Jan 2nd 2010, 06:40 AM
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!