Modular Arithmetic

Daniel123 · 2008-10-19 00:40:11

Just started to look at this... and I'm finding it a bit odd.

My book gives all the rules of congruences, which I've proved easily enough. It then gives an example:

"We find the solution of 5x = 2 (mod 7). Multiply by 3 to get to 15x = 6 (mod 7). But 15 = 1 (mod 7), so x = 6 (mod 7)"

Which I think I'm fine with - we multiply by 3 to get something that is congruent to 1 (mod 7), to get the x term on its own.

It then has some questions:

"Find all values of x satisfying the given congruence:"

1. 3x = 5 (mod 7)

Here I thought to do the same as in the example; mutliply by 5 to give 15x = 25 (mod 7) ⇒ x = 25 (mod 7) ⇒ x = 4 (mod 7)

2. 6x = 2 (mod 8)

I can't really see what to do with this?

Thanks.

Last edited by Daniel123 (2008-10-19 00:40:36)

mathsyperson · 2008-10-19 01:10:18

The problem comes up because 6 and 8 aren't coprime, so you won't be able to multiply 6 by something to make equivalent to 1 mod 8.

You can divide the whole question by 2 though:
3x = 1 (mod 4)

And that solves the same way as before.
(If the 2 had been an odd number, it's fairly easy to see there would be no solutions)

Daniel123 · 2008-10-19 02:02:36

Ahh, thanks. The next question is actually 6x = 1 (mod 3), which has no solutions.

EDIT:

I'm really not geting this...

How do you solve 4x = 0 (mod 6)?

Thanks.

Last edited by Daniel123 (2008-10-19 02:27:28)

mathsyperson · 2008-10-19 02:50:27

This is equivalent to 2x = 0 (mod 3).

From here, you can multiply up to get x on its own, like before.
However, the 0 won't change with multiplication, so you can tell you'll end up with x=0 (mod 3) without actually doing anything.

Daniel123 · 2008-10-19 02:59:13

mathsyperson wrote:

This is equivalent to 2x = 0 (mod 3).
From here, you can multiply up to get x on its own, like before.
However, the 0 won't change with multiplication, so you can tell you'll end up with x=0 (mod 3) without actually doing anything.

Which is exactly what I did, but my book gives the answer as "x = 0 or 3 (mod 6)".

?

Daniel123 · 2008-10-19 03:32:38

Another problem...

x^2 = 2 (mod 7)

Thanks.

mathsyperson · 2008-10-19 03:54:23

x=0 (mod 3) is exactly the same as the book's answer, just a more efficient way of saying it.
For the second one, I could well be forgetting something, but the only way I can think of is to check each case.

0² = 0 = 0 }
1² = 1 = 1 }
2² = 4 = 4 }
3² = 9 = 2 } mod 7
4² = 16 = 2 }
5² = 25 = 4 }
6² = 36 = 1 }

Therefore, x = 3 or 4 (mod 7)

Math Is Fun Forum

#1 2008-10-19 00:40:11

Modular Arithmetic

#2 2008-10-19 01:10:18

Re: Modular Arithmetic

#3 2008-10-19 02:02:36

Re: Modular Arithmetic

#4 2008-10-19 02:50:27

Re: Modular Arithmetic

#5 2008-10-19 02:59:13

Re: Modular Arithmetic

#6 2008-10-19 03:32:38

Re: Modular Arithmetic

#7 2008-10-19 03:54:23

Re: Modular Arithmetic

Board footer