Solving Congruences and the Relationship between (p^{l-1}) and (p^{l})

  • Thread starter mhill
  • Start date
In summary, the conversation discusses the possibility of solving the equation f(x)=0 mod(p^{l-1}) and using that solution to solve the equation f(x)=0 mod(p^l). It is mentioned that if it were easy to solve f(x)=0 mod(p), then a solution to (1) could be easily found. However, it is not clear if f(x)=0 mod(p^l) has solutions and if they can be easily found. The concept of Hensel lifting is also mentioned as a potential method for solving the equations.
  • #1
mhill
189
1
if we knew how to solve [tex] f(x)= 0 mod (p^{l-1}) [/tex] (1)

could we solve then [tex] f(x)= 0 mod (p^{l}) [/tex] for integer 'l'

the idea is, if it were easy to solve [tex] f(x)= 0 mod (p) [/tex] then we could easily find a solution to (1) but i do not know how to do it.
 
Physics news on Phys.org
  • #2
It's not even clear that
[tex]f(x)\equiv0\pmod{p^l}[/tex]
has solutions, let alone that we can easily find them.
 
  • #3
http://en.wikipedia.org/wiki/Hensel_Lifting

But don't just immediately click on that link! Think about the problem first. Suppose you knew that f(x) had exactly one root modulo p. (Let's say a is that root) Then isn't there a very narrow range of possibilities for a root of f(x) modulo p^2?
 

FAQ: Solving Congruences and the Relationship between (p^{l-1}) and (p^{l})

What is a congruence?

A congruence is a mathematical relationship between two numbers, where the two numbers have the same remainder when divided by a third number. This relationship is denoted by the symbol ≡ (equivalent to). For example, 7 ≡ 19 (mod 3) means that 7 and 19 have the same remainder when divided by 3.

How is a congruence solved?

To solve a congruence, we need to find the value of the unknown number (usually denoted by x) that satisfies the given congruence equation. This can be done by using different methods such as trial and error, the Euclidean algorithm, or the Chinese remainder theorem.

What is the relationship between (pl-1) and (pl) in congruences?

In congruences, (pl-1) is known as the inverse of (pl). This means that when (pl-1) is multiplied with (pl), the result is equivalent to 1 (mod p). In other words, (pl-1) is the number that, when multiplied with (pl), gives the remainder of 1 when divided by p.

How is the inverse of (pl) calculated in congruences?

The inverse of (pl) can be calculated using the extended Euclidean algorithm. This involves finding the greatest common divisor (GCD) of (pl) and the modulus (p). If the GCD is 1, then the inverse of (pl) exists and can be found using the algorithm. If the GCD is not 1, then the inverse does not exist.

Can congruences be used in encryption algorithms?

Yes, congruences have many applications in cryptography and encryption algorithms. In fact, the RSA algorithm, which is commonly used in secure communication over the internet, is based on the principles of congruences and the relationship between (pl-1) and (pl).

Similar threads

I What is the size of the quotient group L/pZ^m?
Replies
1
Views
2K
I ##(p^k -1) \equiv X \mbox{(mod p)}## via Wilson's theorem
Replies
2
Views
1K
I Proof for subgroup -- How prove it is a subgroup of Z^m?
Replies
11
Views
2K
I Why do the lines m and l coincide in the proof of the parallelogram rule?
Replies
4
Views
2K
About semidirect product of Lie algebra
Replies
19
Views
2K
B Parametric Representation of Lines
Replies
13
Views
2K
I If L is diagonalizable, algebraic & geometric multiplicities are equal
Replies
4
Views
2K
MHB Orthogonal Complement of Polynomial Subspace?
Replies
2
Views
1K
MHB Solve Sets of Form $v+X$ in $\mathbb{R}^2$
Replies
5
Views
1K
MHB Solving Congruences with Polynomials: A Prime Challenge
Replies
5
Views
3K

Hot Threads

Recent Insights

Back
Top