Congruence with Prime Modulus

A single congruence $\pmod{n}$ is equivalent to a set of simultaneous congruences modulo the prime powers $p^e$ appearing in the factorization of $n$.We therefore explore the congruences $\pmod{p^e}$, where $p$ is prime.We will first consider the simplest case $e=1$


Arithmetic in $\mathbb{Z}_p$

We saw  that a linear congruence $ax \equiv b \pmod{n}$ has a unique solution $\pmod {n}$ if $gcd(a,n) = 1$. Now if $n$ is a prime $p$, then $gcd(a,n) =gcd(a, p)$ is either 1 or $p$; in the first case, we have a unique solution $\pmod {p}$,while in the second case (where $p|a$), either every $x$ is a solution (when $p| b$) or no $x$ is a solution (when $p \nmid b)$.

One can view this elementary result as saying that if the polynomial $ax -b$ has degree $d = 1$ over $\mathbb{Z}$, (that is, if $a \ne 0 \pmod {p})$, then it has at most one root in $\mathbb{Z}_p$. Now in algebra we learn that a non-trivial polynomial of degree $d$, with real or complex coefficients, has at most $d$ distinct roots in $\mathbb{R}$ or $\mathbb{C}$; it is reasonable to ask whether this is also true for the number system $\mathbb{Z}_p$, since we have just seen that it is true when $d = 1$. Our first main theorem, due to Lagrange, states that this is indeed the case.

Theorem:Let $p$ be prime and let $f(x) = a_dx^d+ \ldots +a_1x + a_0$ be a polynomial with integer coefficients, where $a_i \not \equiv 0 \pmod{p}$ for some $i$. Then the congruence $f(x) \equiv 0 \pmod{p}$ is satisfied by at most $d$ congruence classes $[x] \in Z_p$.

Congruence modulo prime $p$ can be solved using Fermat's Little Theorem and Euler's Theorem.
 
Willson's Theorem is another useful result in the prime modulo congruence.



Comments

Post a Comment

Popular posts from this blog

Number Theory CST 292 KTU IV Semester Honors Course Notes Dr Binu V P 9847390760

About me Syllabus Scheme Teaching Plan Model Question Paper University Question Papers Assignment-1 Module-1  Introduction Well ordering principle Group Ring Fields Group Ring Fields in detail Divisibility Modular Arithmetic GCD- Euclidean Algorithm Bezout's Identity Extended Euclidean Algorithm LCM-Least Common Multiple Linear Diophantine Equations Modular Division Module-II Prime Numbers and Prime-Power Factorisation Fermat and Mersenne Prime Primality Testing and Factorization Miller Rabin Primality Testing Algorithm Fermat  Factorization Congruence Modular Exponentiation Linear Congruences Simultaneous Linear Congruences- Chinese Remainder Theorem Fermat's Little Theorem and Euler's Theorem Wilson's Theorem Module-III Congruence with Prime modulus Congruence with Prime power modulus Pseudoprime and Carmichael Numbers Euler's Totient Function Cryptography The Group of Units - Primitive Roots Module-IV Quadratic Residues-Legendre and Jacobi Symbols Arithmetic Func...
Read more

Sum of Squares

Image
In this our aim is to determine which integers can be expressed as the sum of given number of squares ie; which have the form $x_1^2+x_2^2+\cdots+x_k^2$, where each $x_i \in \mathbb{Z}$, for a given $k$. Definition: For each integer $k \ge 1$, let $S_k=\{n|n=x_1^2+x_2^2+\cdots+x_k^2$ for some $x_1,x_2,\ldots,x_k \in \mathbb{Z} \}$ , the set of all sum of $k$ squares. Example: $S_1=\{0,1,4,9,\ldots\}$ is the set of all squares. By inspection $S_2$, the set of sum of two squares contains 0,1,2,4,5 and 8 but not 3,6, or 7. Lemma: The set $S_2$ contains, the sum of two squares is closed under multiplication ie; if $s,t \in S_2$ , then $st \in S_2$. Proof:Let $s=a_1^2+b_1^2$ and $t=a_2^2+b_2^2$ be the elements of $S_2$, where $a_1,b_1,a_2,b_2 \in \mathbb{Z}$. Then the identity $$(a_1^2+b_1^2)(a_2^2+b_2^2)=(a_1a_2-b_1b_2)^2+(a_1b_2+b_1a_2)^2$$ This shows that $st \in S_2$ Example: We have $8=2^2+2^2$ and $10=3^2+1^2$ so $8.10=80=(2.3-2.1)^2+(2.1+2.3)^2=4^2+8^2$ Note: an equivalent ident...
Read more