Solving Congruences mod p^e

Suppose that $p$ is prime and $e > 1$. If $x$is a solution of a congruence $f(x) =0 \pmod{p^e}$, then $x$ satisfies $f(x) \equiv 0 \pmod{p}$, so one way of finding all solutions of $f(x) \equiv 0 \pmod {p^e}$ is first to solve the simpler congruence $f(x) = 0 \pmod{p}$,and then to see which solutions of this are also solutions of the more restrictive congruence $f(x) \equiv 0 \pmod{p^e}$. In many cases an effective strategy is to increase the exponent of $p$ one step at a time, solving $f(x) \equiv 0 \pmod{p}$, then $f(x) \equiv 0 \pmod{p^2}$, and so on until we reach the modulus $p^e$. 
 
Example:

We could have solved the congruence in Example more directly by writing it as $2x \equiv 3 + 5^e \pmod {5^e}$; since $3 + 5^e$ is even, and 2 is coprime to 5^e,we get the general solution $c = (3 + 5^e)/2 \pmod {5}$. Instead, we used the longer iterative method to give a simple illustration of how this method works.

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

Well Ordering Principle

In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which $x$ precedes $y$ if and only if  $y$ is either $x$ or the sum of $x$ and some positive integer (other orderings include the ordering $2,4,6$; and $1,3,5$). The phrase "well-ordering principle" is sometimes taken to be synonymous with the "well-ordering theorem". On other occasions it is understood to be the proposition that the set of integers $\{…,−2,−1,0,1,2,3,…\}$ contains a well-ordered subset, called the natural numbers, in which every nonempty subset contains a least element. Well-ordering Principle: If $S$ is a non-empty set of non-negative integers, then $S$ has a least element, i.e., there is an integer $c \in S$ such that $c \le x$ for all $ x \in S$. The principle of mathematical induction follows direct
Read more