1/192 = k mod7
I ran this through Wolfram Alpha and got the answer k=5
I assume that this is because
(192 * 5)/7 has a remainder of 1 (is this correct?)
Is there a good way of finding the 5 manually?
Thankyou.
You're certainly covering some ground Melody !
I don't ever remember mixing reciprocals with modular arithmetic before, so this is something of a first for me.
(Hope it's OK.)
so multiplying this with your equation, we have which implies that for some integer
The smallest (positive) integer value for satisfying this is
Yes. 1/a= b is the same as ab= 1 in any commutative algebraic system.
As for finding 1/192 (mod 7), the first thing you should do is note that 7 divides into 192 27 times with remainder 3, so 192= 3 (mod 7). Finding 1/192 (mod 7) is the same as finding 1/3 (mod 7) which is the same as saying that if x= 1/3 (mod 7) then 3x= 1 (mod 7) and you can just check: 1*3= 3, 2*3= 6, 3*3= 9= 2 (mod 7), 3*4= 12= 5 (mod 7), 3*5= 15= 1 (mod 7), and 3*6= 18= 4 (mod 7). That is, since 3*5= 1 (mod 7), 5= 1/3 (mod 7)= 1/192 (mod 7).
A more general way of solving "x= 1/b (mod a)" is to use Diophantine equations. Of course, "192x= 1 (mod 7)" means that 192x= 1+ 7y for some integer y. So solving 192x= 1 (mod 7) is the same as solving the Diophantine equation 192x- 7y= 1. There are several different methods to do that. Here's what I would do:
7 divides into 192 27 times with remainder 3. That is, 192- 27(7)= 3.
3 divides into 7 twice with remainder 1. That is, 7- 2(3)= 1.
Replacing the "3" in "7- 2(3)= 1" with "192- 27(7)" gives 7- 2(192- 27(7))= 7- 2(192)+ 54(7)= 55(7)- 2(192)= (-2)(192)- (-55)(7)= 1.
That is, one solution to 192x- 7y= 1 is x= -2, y= -55.
So x= -2 (mod 7) which is the same as x= -2+ 7= 5 (mod 7).
It’s the linear congruence 192k=1(mod7) which has the unique (7 is prime) solution:
k=5(mod7)
k=5 by trial and error with a calculator*. The other solutions are k= 5+7, k=5+2x7, k=5+3x7,…
Ex: 192(5+2x7)-1=521x7
*192k-1=7p: try 192k-1, k=1,2,3…, and divide by 7 till you get an integer.
A more general way of solving "x= 1/b (mod a)" is to use Diophantine equations. Of course, "192x= 1 (mod 7)" means that 192x= 1+ 7y for some integer y. So solving 192x= 1 (mod 7) is the same as solving the Diophantine equation 192x- 7y= 1. There are several different methods to do that. Here's what I would do:
7 divides into 192 27 times with remainder 3. That is, 192- 27(7)= 3.
3 divides into 7 twice with remainder 1. That is, 7- 2(3)= 1.
Replacing the "3" in "7- 2(3)= 1" with "192- 27(7)" gives 7- 2(192- 27(7))= 7- 2(192)+ 54(7)= 55(7)- 2(192)= (-2)(192)- (-55)(7)= 1.
That is, one solution to 192x- 7y= 1 is x= -2, y= -55.
So x= -2 (mod 7) which is the same as x= -2+ 7= 5 (mod 7).
Hello again,
My question concerns the Diophantine equation solution.
I can follow HallsofIvy's solution, at least at a very superficial level, but, firstly, I don't understand why it is more general and, secondly, I can't work out how to apply it to other problems.
I am considering
5/286 = x (mod7)
5=286x (mod7)
286/7 = 40 and 6/7 therefore 286 mod7 = 6
6x=5 mod7
6x = 5, 12,19 etc
x=2+7N where N is any integer
ok that's the easy way done with.
--------------------------------------------------
now for the other way.
286x = 7y+5 for some y in the set of integers
286x-7y=5
286/7 = 40 +6/7
286=40(7)+6
286-40(7)=6 (1)
7/6 = 1 +1/6
7 = 6(1) +1
Sub in (1)
7 = 286-40(7) +1
-286+41(7) = 1
286(-1)-7(-41) =1
how does this help???
I'm obviously doing it wrong.
So my 2 questions are
What am I doing wrong and why is this way more general?
Thank you for your patience and your time.
Thanks Soroban,
I really like this setting out but it has lead me to more questions.
Can k ever have a fractional answer for a question similar to this?
"Since a is an integer, (3k-1) must be a multiple of 7." This statement of yours is only true if k is an integer.
Modular arithmetic deals with integers. You are looking for k an integer. But that's not why I called (old joke).
HallsofIvy’s procedure, I think (I generally don’t pay much attention to procedures or formulas without an explanation, but I finally recalled):
Given: ax=b(modm) & (a,m)=1, (a,m) is gcd
From Euclidean algorithm: (a,m)=sa+tm=1*
multiply by b
b=(bs)a+(bt)m → (bt)m=b-(bs)a so (bs) is a sol.
if m is prime it is the only solution modm. If (a,m)>1, there are other sols.
*Euclidean (division) algorithm: a=qm+r, 0 ≤ r < m
Procedure to get (a,m)=sa+tm best illustrated by example (57,21):
57=2(21) + 15,…….. (57,21)=(21,15)
21=1(15)+6,………... (21,15)=(15,6)
15=2(6)+3,……...…….(15,6)=(6,3)
6=2(3),………….....……(6,3)=3
so (57,21)=3
To express (57,21)=3 in the form s(57)+t(21)
15=57-2(21)
6=21-15=21-[57-2(21)]= -1(57)+3(21)
3=15-2(6)=[57-2(21)]-2[-1(57)+3(21)] = 3(57)-8(21)
Appendix: Old Joke. A man calls a friend and says: There's a madman with a gun, hatchet, and a can of gasoline running around your house trying to break in. But that's not why I called.
When I said "more general", I was thinking of situations where you have a much larger "modulus". For example, to solve 3x= 5 (mod 7), the simplest way to do that is to replace x with 0, 1, 2, 3, 4, 5, and 6 and see that 3*4= 12= 5 (mod 7) so that x= 4 is the solution. But if you had 3x= 5 (mod 107) you really don't want to try every number from 0 to 106! Instead note that 3x= 5 (mod 107) means that 3x=107y+ 5 for some integer y. That is the Diophantine equation 3x- 107y= 5. 3 divides into 107 35 times with remainder 2: 107- 35(3)= 2. 2 divides into 3 once with remainder 1: 3- 2= 1. Replacing that 2 with 107- 35(3), 3- (107- 35(3))= 36(3)- 107= 1. Multiplying by 5, 180(3)- 3(107)= 5. So one solution to 3x- 107y= 5 is x= 180, y= 3. Any solution must be of the form x= 180- 107k, y= 3+ 3k.
Examples of the Euclidean algorithm procedure, including OP for k=p/q:
If ax=b(modm) and (a,m)=1, then:
1=sa+tm from Euclidean algorithm,
b=bsa+btm → b-(bs)a = btm.
x=bs is the unique solution modm.
If 7x=8(mod115), (7,115)=1
1=s(a)+t(m)=s(7)+t(115), from Euclidean algorithm
115=16(7)+3
7=2(3)+1, then
1=7-2(3)=7-2[115-16(7)]
1=17(7)-2(115)=sa+tm
s=17, b=8, x=bs=8(17)(mod115)
Another example of the method is the OP: 1/192=k(mod7). If k=p/q, this becomes:
192p=q(mod7), (192,7)=1
1=s(a)+t(m) = s(192)+t(7), from Euclidean algorithm
192=27(7)+3
7=2(3)+1, then
1=7-2(3)=1-2[192-27(7)]
1=-2(192)+55(7)=sa+tm
s=-2, b=q,
p=-2q
The sols are unique mod7 for q=1,2,3,4,5,6,7. If r=q+n7, r=q(mod7) and 192p=r(mod7) has same solution as 192p=q(mod7) by transitivity.
If q=4, p=-2(4)(mod7)=-8(mod7)
Notes:
If ax=b(modm), both a and b can be rational, again leading to an integer congruence: (35/23)x=27/46(mod15) → 70x=27(mod15). I think the OP was giving a hint of this by using (1/192)=k(mod7).
If (a,m)=d >1, the solution becomes a little more involved.
Firstly I want to say thank you to all of you. I really appreciate your efforts to teach me.
What I really needed to know I got out of the first few posts and I am very pleased about that.
---------------------------------------------------------------------
I've spent considerable time this afternoon trying to work out what HallsofIvy and Hartlw are trying to tell me.
To the best of my understanding you are both trying to tell me the same thing.
Maybe I just don't have the pre-knowledge to understand.
I don’t mind if you give up at this point. I have learned what I set out to learn.
However, if you want to continue trying to teach me I will continue to do my best to understand.
----------------------------------------------------------------------
I am looking at this example from Hartlw. (I think that your theory might be beyond me)
Examples of the Euclidean algorithm procedure, including OP for k=p/q:
If ax=b(modm) and (a,m)=1, then:
1=sa+tm from Euclidean algorithm,
b=bsa+btm → b-(bs)a = btm.
x=bs is the unique solution modm.
If 7x=8(mod115), (7,115)=1 What does (7,115)=1 mean ?
1=s(a)+t(m)=s(7)+t(115), from Euclidean algorithm What Euclidean algorithm?
115=16(7)+3 The next 4 lines of number crunching is easy. That's probably the only bit I understand.
7=2(3)+1, then
1=7-2(3)=7-2[115-16(7)]
1=17(7)-2(115)=sa+tm
s=17, b=8, x=bs=8(17)(mod115)
----------------------------------------------------------------------------------------------------------------
Now HallsofIvy,
This was your last post. I split it up so that I could make sense of it.
"When I said "more general", I was thinking of situations where you have a much larger "modulus". For example, to solve 3x= 5 (mod 7), the simplest way to do that is to replace x with 0, 1, 2, 3, 4, 5, and 6 and see that 3*4= 12= 5 (mod 7) so that x= 4 is the solution.
But if you had 3x= 5 (mod 107) you really don't want to try every number from 0 to 106! Instead note that 3x= 5 (mod 107) means that 3x=107y+ 5 for some integer y.
(A) That is the Diophantine equation 3x- 107y= 5. (So far, so good)
(B) 3 divides into 107 35 times with remainder 2: 107- 35(3)= 2. (alright)
(C) 2 divides into 3 once with remainder 1: 3- 2= 1. (alright)
(D) Replacing that 2 with 107- 35(3), 3- (107- 35(3))= 36(3)- 107= 1. (alright)
(E) Multiplying by 5, 180(3)- 3(107)= 5. [Okay, I can see why you did that, but shouldn’t it be 180(3)– 5(107)=5]
So one solution to 3x- 107y= 5 is x= 180, y= 3. Any solution must be of the form x= 180- 107k, y= 3+ 3k.
(F) So one solution to 3x-107y=5 is x=180 and y=5 (alright - if I use my y=5)
(G) Now I am lost.
------------------------------------------------------------------------------
Thanks guys. Your efforts, past and future if you choose are appreciated.
There are three things you have to understand:
1) Definition of congruence
2) Euclidean Algorithm
3) Solution of a linear congruence using the Euclidean Algorithm
2) Euclidean Algorithm:
Theorem: The greatest common divisor ,gcd, of m and n, (m,n), can be found as the last non-vanishing remainder of the Euclidean Algorithm. There exist integers s and t such that (m,n) = sm+tn
The Euclidean algorithm is best explained by examples:
(25,19):
25= 1(19)+6,……(25,19)=(19,6)
19=3(6)+1,………(19,6)=(6,1)=1
6=6(1),…………...
ie, (m,n) doesn’t change. This part is straightforward but a little hard to grasp.
(24,18):
24=1(18)+6…….(24,18)=(18,6)=6
18=3(6)
(24,9):
24=2(9)+6………(24,9)=(9,6)
9=1(6)+3………..(9,6)=(6,3)=3
6=2(3)
(57,21)
57=2(21) + 15,…….. (57,21)=(21,15)
21=1(15)+6,……….. (21,15)=(15,6)
15=2(6)+3,………….(15,6)=(6,3)=3
6=2(3)
The proof of the Theorem resides in the fact that the remainders in the Euclidean Algorithm are constantly decreasing so eventually they reach 0, and (m,n) doesn’t change.
By backward substitution in the above you get (m,n)=sm+tn. In the last example:
3=15-2(6)
6=21-1(15)
15=57-2(21)
which gives (57,21)=3=3(57)-8(21)=s(57)+t(21)
1) & 3) ax=b(modm) has a solution if (b-ax)=km
if (a,m)=1
1=sa+tm from Euclidean algorithm → b=bsa+btm → b-(bs)a=btm
x=bs is a solution. x is unique modm requires more explanation. Enough for now.
If you didn’t understand the other posts, don’t feel bad, neither did I.
Solving congruences (mod n), if they can be solved, depends on divisibility properties of INTEGERS.
One basic fact often established, is that the gcd of two integers, a and b, satisfies what is called a Bezout identity:
If gcd(a,b) = d, then there exist integers r,s with ra + sb = d.
One way to PROVE this, is to actually find the integers r and s. Since it makes no difference what sign a and b have (because their gcd is always positive), we may as well assume b > a > 0 (if one of a or b is 0, then gcd(a,b) = max(|a|,|b|), and if both are 0, there IS no greatest common divisor since ALL integers divide 0).
Hartlw's previous post shows you how to use "long division" to actually find the gcd, and "working backwards", how to find r and s.
If it so happens that gcd(a,b) = 1, this means we have integers r,s such that ra + sb = 1.
Now, if we have an equation:
ak = 1 (mod n), or equvialently: 1/a = k (mod n), we can only solve it if gcd(a,n) = 1.
Why? well suppose gcd(a,n) = d > 1. This means there is some 1 < t < n, and some 1 < u < n with:
dt = a
du = n.
so au = (dt)u = (td)u = t(du) = tn, which means:
au = 0 (mod n).
So if we had some k with:
ak = 1 (mod n), then:
u = u(ak) = (ua)k = (au)k = 0k = 0 (mod n). In other words n divides u, which is impossible since 1 < u < n.
On the other hand, if gcd(a,n) = 1, we can find integers r,s with ra + sn = 1.
Thus:
ra + sn = 1 (mod n)
ra = 1 - sn = 1 (mod n),
and then r (mod n) is the number we are looking for.
Note that this doesn't always work:
1/3 = x (mod 6), equivalent to 3x = 1 (mod 6).
in this case, gcd(3,6) = 3 > 1, so we would expect NO solutions, and indeed:
3*0 = 0 (mod 6)
3*1 = 3 (mod 6)
3*2 = 6 = 0 (mod 6)
3*3 = 9 = 3 (mod 6)
3*4 = 12 = 0 (mod 6)
3*5 = 15 = 3 (mod 6)
If the modulus is PRIME (like 7 in your example) this always works. Every residue mod p has a multiplicative inverse. This is not "obvious".
As an explanation, Hartlw uses the notation (a,b) to mean gcd(a,b), which is common in some texts. I could explain WHY this notation is sometimes used, but I am afraid the explanation would be a bit over your head. Suffice to say that (a,b) is the smallest subset of the integers containing all integers k for which a|k and b|k and is closed under addition and multiplication.
let's use HallsofIvy's example of modulus 107, to find the inverse of 18 (mod 107).
So first we need to find r,s so that:
18r + 107s = 1.
1) 107 = 18*5 + 17
2) 18 = 17*1 + 1
3) 17 = 17*1 + 0 <---remainder vanishes, use previous step
1 = 18 - 17*1 = 18 - 17 <---18 is in our formula, but 107 isn't, yet.
17 = 107 - 18*5 (from step 1)
1 = 18 - 17 = 18 - (107 - 18*5) (substituting 107 - 18*5 in for 17)
1 = 18 - 107 + 18*5 = 18(1 + 5) - 107 = 18*6 - 107
so r = 6, and s = -1.
So, it should be the case that 18*6 = 1 (mod 107). Let's check:
18*6 = 108 = 1 + 107*1, so, yep.
Now we can solve 18x = y (mod 107) for ANY y:
18x = y (mod 107)
6(18x) = 6y (mod 107)
(6*18)x = 6y (mod 107)
x = 6y (mod 107)
In other words, "dividing by 18" in mod 107 is the same as multiplying by 6. This may take some getting used to, since the "18" and "6" in mod 107 do not behave like "ordinary" integers 18 and 6.