Quadratic congruence

  • Thread starter talolard
  • Start date
  • #1
125
0

Homework Statement


How many solutions does [tex]x^{2}\equiv9 mod 7700[/tex] have?
So my question is if this solution is "legitimate"
Solution

First notice that[tex] 7700=7\cdot11\cdot2^{2}\cdot5^{2}[/tex]

Thus we must solve the system [tex]\begin{cases}
x^{2}\equiv2 & \left(7\right)\\
x^{2}\equiv9 & \left(11\right)\\
x^{2}\equiv\mbox{1} & \left(4\right)\\
x^{2}\equiv9 & \left(25\right)\end{cases}.
[/tex]
This system is equivelent to
[tex]\begin{cases}
x\equiv\pm2 & \left(7\right)\\
x\equiv\pm9 & \left(11\right)\\
x\equiv\pm1 & \left(4\right)\\
x\equiv\pm9 & \left(25\right)\end{cases}. [/tex]
since gcd(1,p)=1 is always true, all of these equations are solvable by the fundamental theorem of modulo arithmetic. There are [tex]2^{4}=16[tex] disjoint equations and thus 16 distinct solutions.

Each solution must be distinct, since if x solves to different equations, then for instance we would have [tex]x\equiv2\equiv-2\left(7\right)[tex]


Homework Equations





The Attempt at a Solution

 
Last edited:

Answers and Replies

Related Threads on Quadratic congruence

  • Last Post
Replies
0
Views
3K
  • Last Post
Replies
3
Views
2K
Replies
4
Views
4K
  • Last Post
Replies
1
Views
6K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
3
Views
2K
Top