Fun with math/computing problems from Project Euler.
Prime numbers
Greatest common divisor d = GCD(a, b)
Extended Euclidean Algorithm
The extended GCD algorithm states that,
for two natural numbers a
and b
GCD(a, b) = ua + vb
with u
and v
unique natural numbers.
Because u a % a == 0
and v b % b == 0
we can expresse the theorem as
vb % a == 1 % a
ua % b == 1 % b
Congruent numbers
If n
is a natural number, than a
and b
are congruent module n if n
divide their difference
if
n // (a-b) == 0
than
a % n == b % n
we call this the [a]n
the congruent class module n containing a with 0 <= a < n-1
. This class contains all the natural numbers for which their reminder with n
is a
For example the congruent class module 8 containing 5, [5]8 has the following numbers
[..., -11, -3, 5, 13, 21, 29, ...]
and
[3]4 = [..., -1, 3, 7, 11, ...]
[0]7 = [..., -7, 0, 7, 14, ...[
Fermat Little Theorem
If a prime number p
does not divide a
, in other words a
is in [n]p
with n != 0
, thanks to the extended gcd we have
ua + vp = 1
If p
is prime, than for any natural number n
(n^p - n) % p == 0
In other words, n^p
and n
are congruent module p
for any prime number.
Chinese Reminder Theorem
Let a
and b
be natural numbers with gcd(a, b) = 1
, and let c
and d
be arbitrary integers. Then there is a solution to the simultaneous congruences
(x - c) % a == 0
(x - d) % b == 0
Moreover, the solution is unique modulo ab
; that is, if x1
and x2
are two solutions,
then (x1 - x2) % ab == 0
.
Fore example: find an explicit formula for the solution to the two simultaneous congruences
x ≡ a % 131,
x ≡ b % 52
we use the extended GCD to find
xgcd(131, 52) = 1, -25, 63
which means
63*52 ≡ 1 % 131
-25*131 ≡ 1 % 52
and
x = 63*52 a - 25*131 b