Modulo

[bitter magnet]

I'm sorry but wtf does this mean. I don't get it. How can you have multiple remainders with same dividend/divisor

[surreal helm]

1. Do not ping the Moderators, unless someone is breaking the rules.
2. Do not ping the Helper Moderators, unless there is a conflict between helpers.
3. Do not ping other members randomly for help.
4. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
5. Wait patiently for a helper to come along.
6. If the Helper has answered your question, remember to thank them with the Mathematics Ranks bot and close the thread with:

+close
Feel free to nominate the person for helper of the week in #helper-nominations
If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[foggy spade]

a ≡ b (mod c) means that a and b give the same remainder when divided by c. So, you can add any integer multiple of c to any of them and this will still be true.

[bitter magnet]

This is confusing af. 3 mod 9 is 3 right?

[foggy spade]

Yes. Though, we trivially have a ≡ a (mod c) for any a and c.

[bitter magnet]

I don't get the three-bar sign 😭 🙏

[heady briar]

May I cut in? I think I see the issue.

[foggy spade]

As I said above, a ≡ b (mod c) means that a and b give the same remainder when divided by c.

[foggy spade]

Oh, sure!

[bitter magnet]

Yeah

[foggy spade]

I haven't studied number theory, anyway. I only know about this stuff in passing.

[heady briar]

I think there's a confusion between modular congruence and modular reduction.

[bitter magnet]

Big words

I don't know those lol

[bitter magnet]

The meaning is so weird

Like what math rule is that 😭

[foggy spade]

Well, that's just the definition. Like hours on the clock, they are mod 12.

[bitter magnet]

Is the parenthesis really necessary

Or is it okay to remove those

[heady briar]

It's kind of important because we have two very similar notations for two very different ideas.

Especially since I don't know how to type the three bar equals sign.

Modular congruence is a relation, while modular reduction is an operation.

[bitter magnet]

So 12 = 3 mod 9 and 12 ≡ 3 mod 9 have different meanings?

[heady briar]

Yes. Although technically the first one would be 12 mod 9 = 3.

So here's how it works. I'll start with modular congruence because that's what you're working on and because the definition of modular reduction depends on it.

We write a == b (mod n) and say "a is congruent to b mod (or modulo) n" if and only if n | a - b.

And we can prove that this definition is equivalent to a and b having the same remainder after division by n.

To do this, we use Euclidean division. a and b are integers, so supposing neither a nor b are 0, we therefore have a = nq_a + r_a and b = nq_b + r_b, with 0 <= r_a, r_b < n (presuming n > 0).

(If one is 0, WLOG b, then we trivially have that n | a - 0, that is n | a, and therefore a has a remainder of 0 when divided by n.)

Anyway, q_a, q_b, r_a, and r_b are unique integers.

[bitter magnet]

Woah slow down

😭

That's a lot to take in

[heady briar]

Fair.

Just read through it as slowly as you need to and don't be afraid to ask if you don't understand something.

[bitter magnet]

Yeah thanks

Tbh most of math guys have more patience than those tech guys lol

IT guys would just say Google it

😭 😭 😭 😭

But anyways

[heady briar]

That's because programmers always want to finish their program as quickly as possible so they can stop programming and start doing the thing they wrote the program for.

In mathematics, the name of the game is rigor.

[bitter magnet]

Eh idk, most of them ain't got no patience lol

But anyways

😭

[heady briar]

Are you not understanding something?

[bitter magnet]

Lemme read

[bitter magnet]

Yeah i don't get the underscores

😭

But it's okay

I just wanted to understand the problem I faced earlier

So I feel satisfied now lol

[heady briar]

Those indicate subscripts.

[bitter magnet]

Thanks

[bitter magnet]

Ohhh okay

[heady briar]

I mean, I wasn't actually done explaining.

[bitter magnet]

It's okay

I think it's pr9bably enough

I tried to understand my confusion earlier cause i'm reading cryptography

😭

[heady briar]

I think I have a shorthand explanation now that I've fully processed your comp sci background.

[bitter magnet]

Oh sure

[heady briar]

Modular reduction is a%n.

Probably.

Or something like it.

[bitter magnet]

% acts as an operator right?

[heady briar]

I thought you'd understand that better than the math.

This is, like, programming language.

[bitter magnet]

Yeah i used % all the time to check if the number is even or odd 😭

[heady briar]

Right, it's the remainder operator. I don't know if it's technically exactly equivalent to modular reduction, but it's close enough for horseshoes.

[bitter magnet]

But I'm just confused at this part though:

So 12 = 3 mod 9 and 12 ≡ 3 mod 9 have different meanings?

If so, what do they mean? In each? How do we interpret it

[heady briar]

To say 12 = 3 mod 9 is to say that 3/9 = xR12.

That is, some integer x with remainder 12.

That's why the true statement is 12 mod 9 = 3.

[bitter magnet]

Soo 12 = 3 mod 9 is false?

[heady briar]

I feel like all of this would make much more sense to you if you let me finish my explanation.

[bitter magnet]

Okay okay 😭

[heady briar]

So did you get everything I wrote so far?

[bitter magnet]

I don't get the n | a - b part

[heady briar]

"n divides (a - b)".

[bitter magnet]

Oh

Weird symbol

[heady briar]

(a - b)/n is an integer.

[bitter magnet]

Why not /

😭

[heady briar]

Because that's the symbol for division, not the symbol for divisibility.

[bitter magnet]

Ohh

Divisibility

[heady briar]

Yes.

[heady briar]

Like here.

[bitter magnet]

I see i see

[heady briar]

That's also in your book.

[bitter magnet]

I didn't get the euclidean division part until the end

But it's okay

[bitter magnet]

Yeah was confused at that part

[heady briar]

Euclidean division states that if x and y are integers, and y is not 0, there exist unique integers q and r such that x = qy + r and 0 <= r < |y|.

[bitter magnet]

Just wondering why the modulo arithmetic is useful

Like how do we even use it in the real world

[heady briar]

We use it all the time to prove results you probably take for granted.

Like that an odd number plus an odd number is an even number.

Or that primes which are congruent to 3 modulo 4 are not Gaussian prime.

I think there's also a result relating mod 3 or mod 4 to whether a number is a sum of squares?

It's also very useful for deducing properties of large numbers expressed in exponential form, thanks to Fermat's little theorem.

[bitter magnet]

I have a question though, 12 ≡ 3 mod 9 is the same as 3 ≡ 12 mod 9, right?

[heady briar]

Yes, modular congruence is symmetric. That is, if a == b (mod n), then b == a (mod n). The proof is relatively trivial.

[bitter magnet]

I don't get this part though

It says r is the remainder of a / m?

Idk

[heady briar]

Yes, your book is very confused.

[bitter magnet]

🙃

So I shouldn't mind it then?

[heady briar]

Like I said, there's a difference between modular congruence and modular reduction, and your book is actively confusing the two.

[bitter magnet]

Okay okay

[swift ivy]

@bitter magnet

:HelpIcon:| Help Reminder

Hello hakuunnamatataa, this is a friendly reminder that your help request has been inactive for more than 24 hours. If you no longer need assistance, please consider closing the thread using the +close command. This thread will be automatically closed in 3 days if it remains inactive.