Residues and non residues of general quadratic congruences

In summary, for a given range of x in Zn, where n is composite, we can solve the congruence ax² + bx + c ≡ 0(mod n) by using the formula (2ax + b)² ≡ b²-4ac (mod n) to find solutions where y² ≡ z (mod n). However, when dealing with modulo 4an, it is important to consider both 4an and n in order to prove the existence of residues and non-residues as z values. Additionally, it is possible to find a general range of x in Zn where there exists either only residues or non-residues as solutions. Any errors or confusion in this explanation can be
  • #1
smslca
64
0
for a given range of x in Zn , and n is composite , and ax² + bx + c ≡ 0(mod n) and if (4a,n)=1,
I learned that we can solve the congruence by (2ax + b)² ≡ b²-4ac (mod n) ==> y² ≡ z (mod n)

So, if n is composite,

Sometimes I see, modulo 4an, when do we take 4an and n ,

how can we prove , there exists residues and non-residues as z values. for any range of x in Zn
Is there any range of x in general , such that there exists only either residues or non residues as solutions.

If i am wrong or obscure any where in my question , hope will be notified to me.
 
Last edited:
Physics news on Phys.org
  • #2
sorry i messed it up, please help me to delete the post
 

1. What are residues and non-residues in general quadratic congruences?

Residues and non-residues are elements in a set of numbers that satisfy a quadratic congruence. In other words, they are the remainders when a number is divided by a certain integer, known as the modulus. Residues are numbers that have a square root modulo the modulus, while non-residues do not have a square root modulo the modulus.

2. How do you determine if a number is a residue or a non-residue?

To determine if a number is a residue or a non-residue, you can use the Legendre symbol. The Legendre symbol is defined as:

(a|m) =

  • 1 if a is a residue modulo m
  • -1 if a is a non-residue modulo m
  • 0 if a is divisible by m

3. What are the properties of residues and non-residues?

Some properties of residues and non-residues include:

  • If a is a residue modulo m, then a^2 is also a residue modulo m.
  • If a and b are both residues modulo m, then a+b and a-b are also residues modulo m.
  • If a is a non-residue modulo m, then a^2 is also a non-residue modulo m.
  • If a is a residue modulo m, then (-a) is also a residue modulo m.

4. What is the importance of residues and non-residues in number theory?

Residues and non-residues have important applications in number theory, particularly in the field of cryptography. They are used in the RSA encryption algorithm, which relies on the difficulty of factoring large numbers into their prime factors. Residues and non-residues also have connections to other areas of mathematics such as quadratic reciprocity and the distribution of prime numbers.

5. How are residues and non-residues related to primitive roots?

Primitive roots are residues that generate the entire set of residues modulo a given modulus. In other words, if a is a primitive root modulo m, then every residue modulo m can be written as a^k for some integer k. Non-residues, on the other hand, cannot generate the entire set of residues modulo m. This property makes primitive roots useful in solving problems involving quadratic residues and non-residues.

Similar threads

Replies
7
Views
782
  • Linear and Abstract Algebra
Replies
4
Views
3K
  • Precalculus Mathematics Homework Help
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
3K
  • Linear and Abstract Algebra
Replies
4
Views
3K
  • Precalculus Mathematics Homework Help
Replies
5
Views
871
Replies
3
Views
2K
  • STEM Educators and Teaching
2
Replies
36
Views
3K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
5
Views
8K
Back
Top