How can I find 544 mod 3 using congruence

[Mathematicsresear]

Homework Statement

Find 544 mod 3 using congruence

Homework Equations

a mod b and a is congruent to b mod n if and only if n divides a-b

The Attempt at a Solution

[/B]
544=54(10)+3 and we also know that 54 is congruent to 18 mod 3, now I'm not sure how to find the remainder.

 

[PeroK]

Homework Statement

Find 544 mod 3 using congruence

Homework Equations

a mod b and a is congruent to b mod n if and only if n divides a-b

The Attempt at a Solution

[/B]
544=54(10)+3 and we also know that 54 is congruent to 18 mod 3, now I'm not sure how to find the remainder.

Have you ever heard of long division?

 

[Mathematicsresear]

Have you ever heard of long division?

Yes, that's not the problem. The problem is that why can 544 = 54x10 +4 be written as 54x10+4 is congruent to 0(10)+1 mod 3?

 

[PeroK]

Why not just divide 544 by 3?

 

[Mathematicsresear]

Why not just divide 544 by 3?

Because the question requires me to use modular congruences only, plus I'm trying to understand the train of thought that was used in the solution.

 

[PeroK]

Because the question requires me to use modular congruences only.

What's a modular congruence?

 

[Orodruin]

Hint: If $a \sim b$ mod 3, then $ca \sim cb$ mod 3 for all $c$. Use this to write $544 = 5\cdot 100 + 4\cdot 10 + 4$ and compute 100 mod 3 and 10 mod 3.

This is pretty straight-forward to show as $ca-cb = c(a-b) = 3cn$ for some integer $n$.

 

[Mathematicsresear]

What's a modular congruence?

a is congruent to b mod n if and only if n divides a -b

 

[PeroK]

a is congruent to b mod n if and only if n divides a -b

Okay. But, where does that say you can't use long division? In fact, it specifically says "if $n$ divides $a-b$". If that's not an invitation to divide I don't know what is!

 

[Orodruin]

Okay. But, where does that say you can't use long division? In fact, it specifically says "if $n$ divides $a-b$". If that's not an invitation to divide I don't know what is!

Well, one reason to not do it is that it is much much faster to use modular congruence if you know what you are doing here.

 

[Mathematicsresear]

Okay. But, where does that say you can't use long division? In fact, it specifically says "if $n$ divides $a-b$". If that's not an invitation to divide I don't know what is!

I understand, but why is 544 congruent to 0(10)+1 mod 3, where did the 0(10) come from?

 

[Orodruin]

I understand, but why is 544 congruent to 0(10)+1 mod 3, where did the 0(10) come from?

Did you read my post?

 

[Mathematicsresear]

Did you read my post?

I just read it, I'm attempting to solve it now

 

[Mathematicsresear]

Hint: If $a \sim b$ mod 3, then $ca \sim cb$ mod 3 for all $c$. Use this to write $544 = 5\cdot 100 + 4\cdot 10 + 4$ and compute 100 mod 3 and 10 mod 3.

This is pretty straight-forward to show as $ca-cb = c(a-b) = 3cn$ for some integer $n$.

100mod 3 is 1 and 10 mod 3 is 1

 

[Orodruin]

100mod 3 is 1 and 10 mod 3 is 1

Right, and more generally $10^n \sim 1$ mod 3. Given what I said about $ca \sim cb$ mod 3 if $a \sim b$ mod 3, how does this help you to compute 544 mod 3?

 

[PeroK]

I understand, but why is 544 congruent to 0(10)+1 mod 3, where did the 0(10) come from?

If you are trying to find $a \mod n$, then you have two main approaches:

a) Divide $a$ by $n$ to find the remainder.

b) Reduce $a$ by "obvious" multiples of $n$ until you get a remainder.

For example, to find $7,391 \mod 7$, say.

a) $7391/7 = 1055$ remainder $6$ (long division)

b) $7,391 \mod 7 = 391 \mod 7$ (because $7,000$ is divisible by $7$)

$391 \mod 7 = 41 \mod 7$ (because $350$ is divisible by $7$)

$41 \mod 7 = 6 \mod 7$ (because $35$ is divisible by $7$)

Sometimes method b is easier, but if you're not sure what you're doing then you should always check by using long division.

 

[Orodruin]

If you are trying to find $a \mod n$, then you have two main approaches:

a) Divide $a$ by $n$ to find the remainder.

b) Reduce $a$ by "obvious" multiples of $n$ until you get a remainder.

For example, to find $7,391 \mod 7$, say.

a) $7391/7 = 1055$ remainder $6$ (long division)

b) $7,391 \mod 7 = 391 \mod 7$ (because $7,000$ is divisible by $7$)

$391 \mod 7 = 41 \mod 7$ (because $350$ is divisible by $7$)

$41 \mod 7 = 6 \mod 7$ (because $35$ is divisible by $7$)

Sometimes method b is easier, but if you're not sure what you're doing then you should always check by using long division.

I disagree. There are many other approaches. Including the one that I have suggested, which is particularly simple in the case of mod 3 ...

 

[Orodruin]

For example:
10 ~ 3 mod 7
Knowing this, 7391 ~ 0*27 + 3*9 + 6 + 1 ~ 3*2 + 6 + 1 = 13 ~ 6 mod 7.

 

[Mathematicsresear]

For example:
10 ~ 3 mod 7
Knowing this, 7391 ~ 0*27 + 3*9 + 6 + 1 ~ 3*2 + 6 + 1 = 13 ~ 6 mod 7.

Thank you very much! I got it!

 

[Orodruin]

Thank you very much! I got it!

So please share how it works out in the case of 544 mod 3. We cannot comment on the solution to the full solution to the actual problem until you do.

 

[Mathematicsresear]

So please share how it works out in the case of 544 mod 3. We cannot comment on the solution to the full solution to the actual problem until you do.

I did it a bit differently, I said that since 544 is equal to 54(10)+4 and since 54 ~ 0 mod 3 then in order to make the 54(10)+4 term divisible by 3, I must make it congruent to 1 modulo 3. One more question, if I had something along the lines of x is congruent to... which is congruent to b (mod n), what does that mean?

 

[Orodruin]

I did it a bit differently, I said that since 544 is equal to 54(10)+4 and since 54 ~ 0 mod 3 then in order to make the 54(10)+4 term divisible by 3, I must make it congruent to 1 modulo 3.

Yes, that works. However, for 3 (and 9) you have 10^n ~ 1 mod 3 (or 9). This makes it particularly simple to compute congruences for those two numbers as, for example,
544 ~ 5+4+4 = 13 ~ 1+3 ~ 1 mod 3
You simply add the digits of the number together and the result will be congruent to the original number. Rinse and repeat.

Edit: Alternatively you can do a congruence of the digits with 3 first, i.e., 544 ~ 211 ~ 2+1+1 ~ 1 mod 3.

 

[Mark44]

The simplest way for modulo 3 arithmetic is to just add up the digits 544 --> 5 + 4 + 4 = 13 ~ 1 (mod 3)
Another way that I don't think was discussed in the thread is to factor the number, using the idea that if a = b*c, then a (mod m) = b (mod m) * c (mod m)

$544 = 2^5 * 17$ so $544 (\mod~ 3) ~ [2^5 (\mod~ 3)] * 17 (\mod~ 3)$

As a side note, a technique called "casting out 9's" used to be taught as a way to check arithmetic. For example, if you had to do this addition:
35 + 52 + 38 + 28
Let's say you do the addition incorrectly and get 152.
Casting out 9's is equivalent to adding the digits of each number, continuing, if necessary until you get a single digit 0 through 8.
35 --> 8 (i.e., 35 (mod 9) = 8)
52 --> 7
38 --> 2
28 --> 10 --> 1
Add the values to the right: 8 + 7 + 2 + 1 = 18 ~ 0 (mod 9)
Add the digits of the answer we got earlier: 152 --> 8
Since the modular equivalence classes of the addends came to 0, and the modulus of the answer came to 8, there's a mistake.

As an additional side note, there's a fairly easy number theory proof that for a decimal number $D = d_1d_2\dots d_n$, $D (\mod~ 9) = (d_1 + d_2 + \dots + d_n) (\mod~ 9)$.

 

[Orodruin]

Another way that I don't think was discussed in the thread is to factor the number, using the idea that if a = b*c, then a (mod m) = b (mod m) * c (mod m)

I would say this is exactly what the OP used to conclude that 540 ~ 0 mod 3 ...

 

[PeroK]

I did it a bit differently, I said that since 544 is equal to 54(10)+4 and since 54 ~ 0 mod 3 then in order to make the 54(10)+4 term divisible by 3, I must make it congruent to 1 modulo 3. One more question, if I had something along the lines of x is congruent to... which is congruent to b (mod n), what does that mean?

Although there are many tricks and techniques for doing modular arithmetic, fundamentally $a \mod n$ means the remainder when you divide $a$ by $n$.

If you, for whatever reason, don't accept that then this topic is always going to be more difficult and mysterious than it need be.

 

[Orodruin]

Although there are many tricks and techniques for doing modular arithmetic, fundamentally $a \mod n$ means the remainder when you divide $a$ by $n$.

I disagree. The (mod n) should typically go after the entire arithmetic and denotes that the arithmetic was done modulo n, i.e., members on either side of the congruence sign represent the same congruence class. In other words
5 ~ 2 (mod 3) and 2 ~ 5 (mod 3) are both valid congruence relations (we would typically not just write 5 (mod 3) = 2).

That any number is in the same congruence class as its remainder is a different matter. My point is that ”5 (mod 3)” does not mean ”2”. It means the congruence class of 5 modulo 3. We already have a name for the remainder.

 

[PeroK]

I disagree. The (mod n) should typically go after the entire arithmetic and denotes that the arithmetic was done modulo n, i.e., members on either side of the congruence sign represent the same congruence class. In other words
5 ~ 2 (mod 3) and 2 ~ 5 (mod 3) are both valid congruence relations (we would typically not just write 5 (mod 3) = 2).

That any number is in the same congruence class as its remainder is a different matter. My point is that ”5 (mod 3)” does not mean ”2”. It means the congruence class of 5 modulo 3. We already have a name for the remainder.

It's certainly better to say $a = b \ mod \ n$ means $a$ and $b$ have the same remainder when divided by $n$.

The definition of equivalence classes follows. But, you can do modular arithmetic on $\mathbb{Z}$ without considering the set of equivalence classes $\mathbb{Z}_n$.

 

[PeroK]

To illustrate this point, the original question was:

Homework Statement

Find 544 mod 3 using congruence

This is modular arithmetic on $\mathbb{Z}$ - the question is essentially looking for the remainder at this stage. Otherwise, the answer would be, for example:

$544 \ mod \ 3 = \{\dots -5, -2, 1, 4, \dots \}$

Or, whatever.

The OP may not have reached the stage of defining these equivalence classes yet.