Blogs

Basics of number Theory(part-2)

The post starts from where previous ended.

1.Linear Congruence Equations
The equations of the form ax ? b (mod n) where (x is an unknown integer ) are called linear congruences. Such a congruence will have a solution if and only if there exists an integer x such that n | (ax-b), i.e. ax -b = ny for some integer y, or in other words ax + n(-y) = b. We already know from Bezout's identity that a linear diophantine equation like this will have a solution only if gcd of (a,n), say d, divides b. In such a case, let b = dd', a = da', n = dn', so we have:
da'x + dn'(-y) = dd' where gcd(a',n') = 1
Cancelling d throughout,
a'x + n'(-y) = d'.
since gcd of (a', n') = 1, now we can use Extended Euclid's algorithm to find the solution for a'x + n'(-y) = 1. and then multiply this solution by d' to get a solution for a'x + n'(-y) = d'.

Note that if ax ? b (mod n) has a solution, then there is a unique solution mod (n/d). If this solution is denoted by x0, then there are exactly d solutions mod n, given by x0+ kn/d where 0 <= k < d.

2.Chinese Remainder Theorem
Typical problems of the form "Find a number which when divided by 2 leaves remainder 1, when divided by 3 leaves remainder 2, when divided by 7 leaves remainder 5" etc can be reformulated into a system of linear congruences and then can be solved using Chinese Remainder theorem. For example, the above problem can be expressed as a system of three linear congruences: "x ? 1 (mod 2), x ? 2 mod(3), x ? 5 mod (7)".

In general, a system of linear congruences:
x ? a1 (mod n1)
x ? a2 (mod n2)
x ? a3 (mod n3)
....
x ? ak (mod nk)

where (ni,nj) = 1 for every ni != nj has a unique solution modulo n where n = n1n2n3...nk.
Let ci= n/ni for every i. Let di be the solution for the congruence cix = 1 (mod ni) such that 0 <= di < ni. (This solution can be found out using Extended Euclid's algorithm). Then the common solution to the above system of linear equations is given by
c = a1c1d1 + a2c2d2 + ... + akckdk


A direct corollary of the Chinese Remainder theorem is as follows: Let n = p1a1 * p2a2 * .... * pkak be the prime factorization of n. Then, for any integers a and b, we have a = b (mod n) iff a = b (mod piai ) for each i.

The generalization of the Chinese Remainder Theorem, which discusses the case when the ni's are not necessarily pairwise coprime is as follows - The system of linear congruences

x ? a1 (mod n1)
x ? a2 (mod n2)
x ? a3 (mod n3)
....
x ? ak (mod nk)

has a solution iff gcd(ni,nj) divides (ai-aj) for every i != j. In such a case, there is a unique solution mod n, where n is the least common multiple of n1,n2...nk

3.. Quadratic Congruences
Given q and n, if the quation x2 ? q (mod n) has a solution, then q is called quadratic residue modulo n. If this equation doesnot have a solution, then q is called "quadratic non residue" modulo n. For example, x2 ? 9 (mod 15) has a solution x = 12, hence 9 is a quadratic residue modulo 15. On the other hand, the equation x2 ? 11 (mod 15) has no solution, hence 11 is a quadratic non-residue modulo 15. In simpler terms, an integer q is a quadratic residue modulo n if a square can take the form (nk+q) for some positive integer n.

Finding whether a quadratic congruence having prime number modulus has a solution or not is somewhat easy: x2 ? a (mod p) has a solution only if a(p-1)/2 = 1 (mod p). In such a case, the Shank-Tonelli algorithm can be used to get the solution.



For Authors Only: