Math - Others
- Modular Arithmetic
x ≡ y mod n
- If both x and y have same remainder when divided by n
- If n divides (x-y)
- If
x ≡ y mod n & a ≡ b mod n then
- (x+a) = (y+b) mod n
- (x-a) = (y-b) mod n
- (x*a) ≡ (y*b) mod n
- If
x ≡ (y + z) mod n then
- x ≡ (y mod n * z mod n) mod n
- x = (y mod n) + (z mod n)
- Euler's Toient Function
- Φ(n) for (n≥1) is defined as the number of positive integers less than "n" that are co-prime to "n"
- When "n" is prime
- When "a" & "b" are co-prime
- Multiplicative Inverse
x ≆ 0 mod n => "n" is prime
- x.y ≡ 1 mod n => "y" is multiplicative inverse of "x"
- y = x-1 mod n => "y" is multiplicative inverse of (x mod n)
- If "n" is not prime then "x" & "n" should be co-prime
- Euler's Theorem
- xΦ(n) = 1 mod n => "x" & "n" should be co-prime
- xΦ(n)*a = 1 mod n
- Fermat's Theorem
- Special case for Euler's Theorem
- xn-1 ≡ 1 mod n
- "n" is prime, "x" is not divisible by "n" =>
x ≆ 0 mod n
- xΦ(n)+1 = x mod n
- xn = x mod n => "x" & "n" should be co-prime