existence of proof in connection to x^2 = y^2 mod n

**poserp** · Nov 12th 2008, 06:58 PM

Let x^2 be less than some integer N. Has anyone proved whether or not there are solutions to y^2 = x^2 mod N for all x^2 <= N?

For example, if N = 27 are there solutions to all of these congruences:

y^2 = 4 mod 27
y^2 = 9 mod 27
y^2 = 16 mod 27
y^2 = 25 mod 27

**whipflip15** · Nov 13th 2008, 04:01 PM

Yes namely 2 ,3, 4 and 5 but if you mean two solutions than the answer is also yes because -2, -3, -4, -5 are also solutions.

However there may be even more solutions because Z27 is not a field. If We are working in a field then the polynomial x^2-4 can have at most two roots but in Z_27 it can have more.

EG 1 has 4 square roots in Z8 but only two in Zp for prime p.

**poserp** · Nov 13th 2008, 04:24 PM

Er, forgot to add -- x != y and y^2 > N.

Thread: existence of proof in connection to x^2 = y^2 mod n

LinkBack

Thread Tools

Display

existence of proof in connection to x^2 = y^2 mod n

Similar Math Help Forum Discussions

Proof of the existence of a function f such the f(x)=f'(x)

Proof theory: example of an existence proof of a proof?

[SOLVED] Existence proof

existence proof, how to start?

proof of existence of z in x < z < y

Search Tags