Solve the Congruence (Discrete Math)

[erok81]

Homework Statement

Solve the congruence 2x≡7 (mod 17)

Homework Equations

None.

The Attempt at a Solution

I think my main problem with this is I am still confused on what modulo actually means. But I'll save that for some other time.

So here is what I have done so far.

I found the gcd using the Euclidean Algorithm which was 1 and therefore also has an inverse.

gcd(7,17,)=1

Next working backwards I obtained the inverse which was 5.

This is where I am stuck. I've tried looking at examples, but I am still not getting it. The texts starts with multiplying both sides by by the inverse which gives me 5·2x ≡ 5·7 (mod 17)

Any idea where to go next?

 

[Dick]

5 is the inverse of 7 mod 17. You don't want to multiply both sides by that. You want to multiply by the inverse of 2 mod 17.

 

[Mark44]

Homework Statement

Solve the congruence 2x≡7 (mod 17)

Homework Equations

None.

The Attempt at a Solution

I think my main problem with this is I am still confused on what modulo actually means. But I'll save that for some other time.

Saving that for another time is not a good idea. The equation 2x \equiv 7 (mod 17) says that if you divide 2x by 17, the remainder is 7. We don't care about the quotient, just the remainder. So any number divided by 17 will have a remainder of 0, 1, 2, 3, 4, ... , 15, or 16.

I think my main problem with this is I am still confused on what modulo actually means. But I'll save that for some other time.



So here is what I have done so far.

I found the gcd using the Euclidean Algorithm which was 1 and therefore also has an inverse.

gcd(7,17,)=1

Next working backwards I obtained the inverse which was 5.

The inverse of what? You should say that you are finding the inverse of 7, which is 5. The reason is that 5 * 7 = 35 \equiv 1 (mod 17). (35 = 2 * 17 + 1, so 1 is the remainder.)
Since the product of 5 and 7 is 1 (using modular multiplication), then 5 and 7 are inverses.

This is where I am stuck. I've tried looking at examples, but I am still not getting it. The texts starts with multiplying both sides by by the inverse which gives me 5·2x ≡ 5·7 (mod 17)

Any idea where to go next?

 

[erok81]

Saving that for another time is not a good idea. The equation 2x \equiv 7 (mod 17) says that if you divide 2x by 17, the remainder is 7. We don't care about the quotient, just the remainder. So any number divided by 17 will have a remainder of 0, 1, 2, 3, 4, ... , 15, or 16.

I know it's a bad idea. As soon as learn this (last problem on the homework) I am going to go back through and master it. Which is kind of backwards I suppose.

But now that you typed that out it makes sense. My professor compared it to clock arithmetic. With that and your post I get it now.

The inverse of what? You should say that you are finding the inverse of 7, which is 5. The reason is that 5 * 7 = 35 \equiv 1 (mod 17). (35 = 2 * 17 + 1, so 1 is the remainder.)
Since the product of 5 and 7 is 1 (using modular multiplication), then 5 and 7 are inverses.

Sloppy on my part. I was trying to follow examples in the text. Now I see I should be referencing which inverse I am looking for. I'll practice a few more inverse problems as well.

Now for the x. How do we go about solving for the x?

 

[Mark44]

Multiply both sides of the equation 2x \equiv 7 (mod 17) by the inverse of 2. The inverse of 2 (in modulo 17) is a number b such that b*2 \equiv 1 (mod 17). You should be able to figure it out by trial and error by going through the 17 possible numbers (0, ..., 16) and doubling them. Find the doubled number that has a remainder of 1 when you divide by 17.