"School Thread" or "Math + Seil = *headdesk*"

[The Artist Formerly Known as Hawk]

Originally Posted by Sithdarth

Ok so here's a quick primer on modular (congruence) arithmetic. Basically it goes like this:
a ≡ b mod m ↔ a - b = k*m where a, b, m, and k are all integers.

So for example:
5 ≡ 2 mod 3
5 ≡ 1 ≡ -3 mod 4
5 ≡ -1 mod 6

Basically if a = q*m + r, 0 ≤ r ≤ (m-1) then a - r = q*m and a ≡ r mod m where r is called either the remainder or the least non-negative residue of a mod m.

Now there are some nice rules for modular arithmetic. For example, if a ≡ b mod m and c ≡ d mod m then:
a + c ≡ b + d mod m
a - c ≡ b - d mod m
a*c ≡ b*d mod m

Here are a few examples:
What is the remainder when 123*257*425 is divided by 7?
123 ≡ 4 mod 7
257 ≡ 5 mod 7
425 ≡ 5 mod 7

123*257*425 ≡ 4*5*5 = 100 ≡ 2 mod 7
So the remainder is 2.

What is the remainder of 37*77 when divided by 39?
37 ≡ 37 mod 39 and 37 ≡ -2 mod 39
77 ≡ 38 mod 39 and 38 ≡ -1 mod 39

37*77 = (-2)(-1) ≡ 2 mod 39
So the remainder is 2.

Just one more rule now:
If n > 0 and a ≡ b mod m then a^(n) ≡ b^(n) mod m
So for example:
What is the remainder when 2^(13) is divided by 33?

2^(5) ≡ 32 ≡ -1 mod 33
2^(13) = (2^(5))^2 * 2^(3) = (-1)^(2) * 8 ≡ 8 mod 33
So the remainder is 8.

Just for fun here is Little Fermat's Theorem:
Given a prime integer P two things must be true:

i) For any integer a, a^(P) ≡ a mod P
ii) If a is not a multiple of P then a^(P-1) ≡ 1 mod P

With this you have the mathematical foundation to understand RSA encryption which I'll write up later.

PS: That's only a small fraction of what I've learned about modular arithmetic this semester. There are ways to do pretty much all of the equation solving you do normally with modular arithmetic which can solve some pretty unusual problems. Then of course we moved into fractals. I'm contemplating back tracking a bit and showing you some of the spherical and hyperbolic geometry I did this semester too.

God damn that's a lot of maths. I have only 2 questions;

a) Is any of it revelvant to making time travel possible?

and b) Is any of it relevant to making the flying car possible?

[Wigmund]

Originally Posted by Hawk

God damn that's a lot of maths. I have only 2 questions;

a) Is any of it revelvant to making time travel possible?

and b) Is any of it relevant to making the flying car possible?

No, as a) involves hitting one's head on a toilet seat and stealing plutonium from Libyans, and b) involves using a) to travel into the future and steal flying car technology to return to now so that b) will be possible so that you can use a) to travel into the future to steal b).

[Sithdarth]

Originally Posted by Fungrus

That's pretty interesting actually, but don't you do physics? What part of physics is modular arithmetic needed for?

Well it's actually closely tied to group theory which is important to the Standard Model as well as String and M-theory. As the resident string theorist at my College would say "Theoretical Physics is a science locally isomorphic to Mathematics." On top of that I picked up a secondary major in Mathematics so now I do as much Math for Math's sake as I do Math for Physic's sake.

Originally Posted by Hawk

God damn that's a lot of maths. I have only 2 questions;

a) Is any of it revelvant to making time travel possible?

and b) Is any of it relevant to making the flying car possible?

I don't know, maybe. It depends on what string and M-theory come up with and how important group theory becomes to them. It is however the very foundation of RSA (also known as Public Key) encryption which is what every bank ever uses to do transactions and keep your information safe. Without modular arithmetic we wouldn't have online banking. Hell we wouldn't have online stores or anything else online having to do with finances. Speaking off I'll see about getting a little primer on RSA encryption written up.

Originally Posted by Seil

To Mr. Sithdarth, my rebuttal:

*picture removed*

Well that's just because you haven't learned to love Math yet.

Edit: Ok so here is a little bit on RSA encryption:
The first thing you need is a couple of secret numbers that you tell no one.
You will need two prime numbers with as many digits as possible, let's call them p and q, and an integer N greater than zero such that gcd(N,(p-1)(q-1)) = 1. (That is to say N and the product (p-1)(q-1) have no common factors.)

Then you use these numbers to find an integer M such that M*N ≡ 1 mod (p-1)(q-1). There is a very easy way to do this using the Euclidian Algorithm.

The Euclidian Algorithm works like this:
If a=q*b + r then gcd (a,b) = gcd (b,r) (gcd stands for greatest common divisor)
Which means you can work out a gcd like this:
a = q1*b + r1
b = q2*r1 + r2
r1 = q3*r2 + r3
r2 = q4*r3 + r4
and so on until you hit zero

Some examples:
Find gcd (252,198)
252 = 198*1 + 54
198 = 54*3 + 36
54 = 36*1 + 18
36 = 18*2 + 0
So gcd(252,198) = 18

Now we can use this to write gcd(252,198) as a linear combination of 252 and 198 by running the algorithm backwards like so:
18 = 54 - 36*1 (from the third equation)
36 = 198 - 54*3 (from the second equation)
Putting them together:
18 = 54 - (198 - 54*3)
18 = 54*4 - 198
54 = 252 - 198*1 (from first equation)
Putting the last two above together gives:
18 = (252 - 198*1)*4 - 198
18 = 252*4 - 198*5
And thus is 18 written as a linear combination of 252 and 198.

Now you can use this procedure to find an M such that M*N ≡ 1 mod (p-1)(q-1). For example:
Let p = 11, q = 13, and N = 7 then:
M*7 = 1 mod (10*12)
7*M +z*120 = 1
120 = 7*17 + 1
7 = 1*7 + 0
Then writing 1 as a linear combination of 120 and 7 we have:
120 - 7*17 = 1 so M = -17 ≡ 103 mod 120 (120 - 17 = 103)

Now that you have M you publish it and the product p*q (but never p or q by themselves). So when someone wants to send you a message say a number X they do it like so:
Y = X^(M) mod (p*q) where Y is the number they send you (which must be reduced by modular arithmetic so that is less than p*q) and X is the number they wanted to encrypt.
Then to decode the message you do this:
Y^(N) mod (p*q) where N is your secret exponent. This will give you back the original X.

To continue from the example above say someone wants to send you the letter C and you agreed previously that A = 0, B = 1, C = 2, and so on. Thus:
Y = 2^(103) mod 143 (since 11*13 = p*q = 143)
At which point we are going to need a method called repeated squaring to get to Y which goes something like this:
2 ≡ 2 mod 143
2^2 ≡ 4 mod 143
2^4 ≡ 16 mod 143
2^8 ≡ 256 ≡ 113 mod 143
2^16 ≡ 113^2 ≡ 12769 ≡ 42 mod 143
2^32 ≡ 42^2 ≡ 1764 ≡ 48 mod 143
2^64 ≡ 48^2 ≡ 16 mod 143

2^103 = (2^32)^(3) * 2^(4) * 2^(2) * 2^(1) = 48^2 *48 *16 * 4 *2 = 16 * 16 * 48 * 4 * 2 = 113 * 48 * 4 * 2 = 43392 ≡ 63 mod 143
Thus they send you Y = 63.

Then to get back the message you do this:
63^7 mod 143
63^2 ≡ 108 mod 143
63^3 ≡ 83 ≡ -60 mod 143
63^4 ≡ 81 ≡ -62 mod 143

63^7 = 63^4 * 63^3 = (-60)(-62) = 3720 ≡ 2 mod 143
Thus you have decoded 63 into 2 and know that they send you the letter C.

That in a nutshell is RSA encryption.

[The Artist Formerly Known as Hawk]

I don't know, maybe. It depends on what string and M-theory come up with and how important group theory becomes to them. It is however the very foundation of RSA (also known as Public Key) encryption which is what every bank ever uses to do transactions and keep your information safe. Without modular arithmetic we wouldn't have online banking. Hell we wouldn't have online stores or anything else online having to do with finances. Speaking off I'll see about getting a little primer on RSA encryption written up.

... I'll take that as a "No" then.