Question

given x ≡ 1 (mod 3). Is x ≡ 4 (mod 3) true?

Answer 1

Below is not required but it helps in relating congruences and divisibility

\[x\equiv 1 \pmod 3 \implies 3 \mid (x-1) \implies 3\mid [(x-1) - 3] \\\implies 3\mid (x-4)\implies x\equiv 4\pmod{3}\]

Answer 2

modulo 3 looks like
[0,1,2]
though?

Answer 3

like on
x ≡ 1 (mod 3).
it's x is congruent to the remainder 1 in modulo 3. I can see that part... it's x ≡ 4 (mod 3) that's giving me a hard time... because that's x is congruent to the remainder 4 in modulo 3.

Answer 4

Notice that \(3\mid (3k)\). This is same as saying \(3k\equiv 0 \pmod{3} \).

Therefore \(x\equiv x+0\equiv x+3k\pmod{3}\)

Answer 5

so basically I can add multiple of 3 on either sides, and it still holds?

Answer 6

like
x + 3 ≡ 1 (mod 3) holds?

Answer 7

Yes, congruence is just a neat notation that hides the messy divisibility rules

Answer 8

\(x\equiv y\pmod{n}\) and \(y\equiv z\pmod{n}\) implies \(x\equiv z\pmod{n}\)

transitive property holds, so you can replace \(3\) by \(0\) in modulo 3

Answer 9

Whenever I use mods I end up just subtracting off the number until I have some number less than what I want, like this:

\[9 \equiv 5 \equiv 1 \mod 4 \]
So here I just kept subtracting 4 off, rather than trying to think "ok what's the remainder if I divide by 4?"

There are a bunch of cute tricks you can use too, like:

\[100^{2523672} \mod 3\]

just rewrite 100 as 3*33+1 and we have:

\[(3*33+1)^{klfaljag} \mod 3\]
\[(0*33+1)^{lsdjf0aug} \mod 3\]
\[1 \mod 3\]

Answer 10

ok. I know it seems kinda trivial but I just want to make sure I really understand it.

x + 3k ≡ 1 + 3s (mod 3), for some integer k,s, holds ? right? ^^

Answer 11

actually for *all* integer s,k

Answer 12

x + 3k ≡ 1 + 3s (mod 3)

thats not so important, all you need to do is to refer back to the definition :
\[a\equiv b\pmod{n}\iff n\mid (a-b)\]

Answer 13

@Empty i'm not quite there yet but I might find that useful one day ^^

Answer 14

the moment you see 3k, and if you're in modulo 3, you see that 3k is divisible by 3 :
\[3\mid (3k) \iff 3k\equiv 0 \pmod{3}\]

so you replace \(3k\) by \(0\)

Answer 15

A way to help think of it is all even and all odd numbers can be represented as 2n or 2n+1. So you can see in mod 2, all even numbers are 0 and all odd numbers are 1.

Answer 16

@ganeshie8 ah i see.
x ≡ 4 (mod 3)
x ≡ 1 + 3 (mod 3)

and since 3 is a multiple of 3, replace 3 with 0.

x - 99 ≡ 1 (mod 3). And since 99 is also a multiple of 3, replace it with 0.

and x + 3k ≡ 1 + 3s (mod 3), replace 3k and 3s with 0.

Answer 17

Yes, but careful, congruence relations don't work in both directions always

Answer 18

```
given x ≡ 1 (mod 3). Is x ≡ 4 (mod 3) true?
```

you should start with whats given, not what you want to prove

Answer 19

ah yes. I just need to see what you can validly add to either side (or both).

So in general,
a ≡ b (mod c)

implies a ≡ b + kc (mod c)
implies a + kc ≡ b (mod c)
implies a + kc ≡ b + sc (mod c)

Answer 20

Yep, adding/subtracting a multiple of "c" to a side(s) wont change the congruence because :

\[c\mid (a-b) \implies c\mid [(a-b) + kc]\]

Answer 21

"."

Answer 22

yep! I understand everything now. Thank you!

Answer 23

np