Modular maths question.

Graham2013

Sorry Guys if this forum is not deemed appropriate for my question but I could not find another suitable one on the web!

I was watching an episode of School of Hard Sums where a question set was answered using Modular maths.

I could understand the straightforward answers eg: 13-1(mod3)=0 but not:

2-1(mod3)=1

0-13(mod3)=2

Can some explain how these answers are achieved.

Many thanks
Graham

wealdroam

No, wrong board.

This is a money saving board.

From the rules:

Non-MoneySaving topics
If you want to discuss a subject that's not MoneySaving then there's an area of the Forum set up for it. Read more about the MoneySavers' Arms.

bod1467

But since such questions have been asked here in the Techie board before ...

2 - 1 (mod 3)
2 - 1 = 1
Integer of (1/3) = 0
0 * 3 = 0
1-0=1

0 - 13 (mod3)
0 - 13 = -13
Integer of (-13/3) = -4
-4 * 3 = -12
-13 - -12 = -13 + 12 = -1

So the 2nd answer you gave (2) is incorrect. If in doubt, try it on a Programmer calculator.

paddyrg

A good mental model is a clockface - it wraps around on itself, so after 12 comes 1 (13 mod 12). It's the remainder of a division, so if you imagine 15 mod 12 gives 3 (3pm) because 15 divided by 12 is 1, remainder 3. 40 mod 12 is 40/12 is 3 remainder 4, so 40 mod 12 is 4

The field is quite interesting - it is absolutely core to cryptography. Great article from 2600 Magazine here (reproduced with permission) http://yatta.co.uk/encryption/ showing how modular arithmetic is fundamental to perfect, pure encryption

Graham2013

Thanks guys.

The following website:

ptrow com/perl/calculator pl (I cannot post a link as a Newbie.)

Calculates:

0-13(mod3)=2 (As given on the show)

I searched the web for answers before submitting my post and it would seem Modular arthimatic can display different answers depending on software used (Eg: Excel, Lotus).

Graham

paddyrg

Clockface...

.....0
. /....\
2

---

1

(dots for spacing - this forum compresses them which is why this looks awful)

13 Mod 3 - start at 0 and count round clockwise - so 0(0), 1(1), 2(2), 3(0), 4(1), 5(2),...13(1) - 13 comes to 1

-13 Mod 3 - start at 0 and count anticlockwise
0(0), -1(2), -2(1), -3(0), -4(2)... -13(2) so -13 comes to 2

It's a great, often counterintuitive field.

securityguy

bod1467 wrote: »

0 - 13 (mod3)
0 - 13 = -13
Integer of (-13/3) = -4
-4 * 3 = -12
-13 - -12 = -13 + 12 = -1

So the 2nd answer you gave (2) is incorrect. If in doubt, try it on a Programmer calculator.

When working in a finite field of order n, the results are always in the range 0..(n-1). So you will never have negative results. The method you're using works for addition, but not for subtraction. The field you are working in has 5 elements (-2, -1, 0, 1, 2) rather than the 3 elements (0, 1, 2) implied by operations modulo 3.

Think about a clock, which is a good model for a finite field of order 12. If it is 1 o'clock, and I ask you for what the time was two hours ago, what is the answer? 11 o'clock. Not -1 o'clock.

And if you want to be all techy and !!!!:

bash-3.2$ perl -e 'print ((0-13)%3, "\n")'
2
bash-3.2$ 

bod1467

Try -13 mod 3 in Windows calculator, in Programmer or Scientific mode - tell me what result you get.

esuhl

paddyrg wrote: »

Clockface...

.....0
. /....\
2

---

1

(dots for spacing - this forum compresses them which is why this looks awful)

I'm lost... (but I want to watch the TV programme now!).

Anyway, you can use the CODE tags to use a fixed space font. Like this:

12345678901234567890123456
abcdefghijklmnopqrstuvwxyz
..........................

securityguy

bod1467 wrote: »

Try -13 mod 3 in Windows calculator, in Programmer or Scientific mode - tell me what result you get.

If it gives a negative answer, then it's a remainder, not a residue.

"Modulo" is not the same as "remainder".

See here: https://en.wikipedia.org/wiki/Modulo_operation

Given two positive numbers, a (the dividend) and n (the divisor), a modulo n (abbreviated as a mod n) is the remainder of the Euclidean division of a by n. For instance, the expression "5 mod 2" would evaluate to 1 because 5 divided by 2 leaves a quotient of 2 and a remainder of 1, while "9 mod 3" would evaluate to 0 because the division of 9 by 3 has a quotient of 3 and leaves a remainder of 0; there is nothing to subtract from 9 after multiplying 3 times 3. (Notice that doing the division with a calculator won't show you the result referred to here by this operation, the quotient will be expressed as a decimal fraction.) When either a or n is negative, this naive definition breaks down and programming languages differ in how these values are defined. Although typically performed with a and n both being integers, many computing systems allow other types of numeric operands. The range of numbers for an integer modulo of n is 0 to n − 1.