Quote:
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?