Chinese remainder theorem (CRT) question, flat shapes

[fishturtle1]

Homework Statement

By hand, find the 4 square roots of 340 mod 437. (437 = 23 * 19).

Homework Equations

Chinese remainder theorem (CRT)

The Attempt at a Solution

So this is the wrong way I did it was first I solved $x^2 \equiv 340 (\operatorname{mod} 19)$ and $x^2 \equiv 340 \operatorname{mod} 23)$ which yielded $x \equiv \pm 6 (\operatorname{mod} 19)$ and $x \equiv \pm 8 (\operatorname{mod} 23)$.

So I rewrote these as
1) $x = 6 + 19l$
2) $x = -6 + 19m$
3) $x = 8 + 23n$
4) $x = -8 + 23t$
where $l,m,n,t$ are integers.

And I realized that if you replaced $x$ with $y$ and $l,m,n,t$ with $z$, then you'd have four 2 dimensional lines and you'd have 4 intersection points... and the problem said 4 solutions so I thought this may be something? (but this lead me to decimal solutions and yeah it didn't get me anywhere...)

But today I realized that $l,m,n,t$ are all different(even though they are just arbitrary integers?) so I can't replace them by 1 variable, basically this is a "5 dimensional system of equation" right?

so a couple questions..
1) We have 4 lines in 5 dimensional space. 1) intersects with 3) at some point and 4) at some point. 2) interacts with 3) at some point and 4) at some point. But our solutions are another 4 other lines that look like$x = 220 + 437j$, where j is an integer, etc. So that seems kind of weird that we're looking for a point of intersection as our solution, and then we turn that point into a line?? What is happening here?

Edit: I guess to answer 1), we find the point of intersection $p$, and then take $p \operatorname{mod} 437$ to find its congruence class, and that will give us all our solutions.

2) I know two lines intersect at a point (not parallel lines) and two planes intersect at a line (not parallel planes). So do n dimensional flat objects interaction at some n-1 dimensional flat object? How would you define flat?

edit2: I've been looking at the wiki for flat/flatness and there's a lot of words I don't know, maybe a better question would be what tools do I need to define flat?

EDIT3: Ok i think I've answered my own question, flat was not the right word. I meant linear. Given some $l_1: a_1x_1 + a_2x_2 + ... + a_nx_n = c_1$ and $l_2: b_1x_1 + b_2x_2 + ... + b_nx_n = c_2$ where $a_i , b_i, c_1, c_2$ are constants and $x_i$'s are unknowns. Then our solution is some $2$ dimensional plane. I think my confusion is clear so i'll mark this as solved.. for now...
PS: I did realize that to do this problem, I keep those lines as congruences, and solve them 2 at a time. I was able to work out the 4 solutions: 222, 291, 215, 146 (mod 437).

 

[mighty2000]

Hi there!

I would approach this problem using the Chinese remainder theorem (CRT). This theorem states that if we have a system of congruences, we can combine them to find a single congruence that is equivalent to all of them. In this case, we have the congruences $x^2 \equiv 340 (\operatorname{mod} 19)$ and $x^2 \equiv 340 (\operatorname{mod} 23)$. Using CRT, we can combine these to find a single congruence $x^2 \equiv 340 (\operatorname{mod} 437)$.

To do this, we first need to find the modular inverses of 19 and 23 mod 437. These are 231 and 261, respectively. Then, we can use the CRT formula to find the solution:
$$x \equiv 340 \cdot 231 \cdot 23 + 340 \cdot 261 \cdot 19 (\operatorname{mod} 437)$$
This gives us the four solutions of 222, 291, 215, and 146 (mod 437) that you found.

To address your questions:

1) The solutions to our congruence equation are indeed points in 5-dimensional space. However, since we are working with congruences, we only care about the solutions mod 437. This means that we are essentially working on a 1-dimensional line in 5-dimensional space, since the solutions will repeat every 437 units.

2) In general, n-dimensional objects will intersect at n-1 dimensional objects. For example, two lines intersect at a point, two planes intersect at a line, etc. In this case, our 5-dimensional space is made up of congruences, so we are finding the point of intersection (solution) mod 437.

I hope this helps! Let me know if you have any other questions.