help needed

freddogtgj · 2007-02-28 01:34:16

Find all solutions of the equation x^2 = 2 (a) in Z17; (b) in Z19.

Any ideas?

Ricky · 2007-02-28 03:16:50

Is there a technique you should be using? These numbers are small enough to check by hand, so simple trial an error is possible. But there is probably a theorem somewhere that will help you out. Problem is so many number theory theorems are fairly obscure, it's hard to keep track of them.

John E. Franklin · 2007-02-28 07:01:45

Do they mean 1.414213 and -1.414213i, where i is

?

What is Z19, and Z17 ?

Woops, -1.414213i squared is (-1.414213)^2 times i^2, which goes negative, so that's wrong.

How about just negative 1.414213 ? That would work, as well as positive 1.414213 .

Last edited by John E. Franklin (2007-02-28 07:03:50)

Sekky · 2007-02-28 07:55:53

For Z17 : 6^2 = 2

For Z19: 18^2 = 2

That was by inspection, but I'm not sure how to do it otherwise.

Edit: Z17 has a second solution: 11^2 = 2

Last edited by Sekky (2007-02-28 07:58:31)

JaneFairfax · 2007-02-28 09:14:04

Umm, 18[sup]2[/sup] is 1 in

, I make it.

Note that if x=n is a solution to x[sup]2[/sup] = 2 in

, x=n+17k will also be a solution for any integer k. Since x=6 and x=11 have been found to be solutions, the solution set is therefore .

Similarly for

.

EDIT: Wait. I dont think theres a solution at all in

. Is there?

Last edited by JaneFairfax (2007-02-28 09:32:52)

Ricky · 2007-02-28 10:56:48

What is Z19, and Z17 ?

Pronounced, "Integers modulo n", it is the quotient group formed by modding out multiples of n from the integers. But I'm sure that didn't make sense, so here is a more thorough explanation.

We consider two integers equivalent when their remainder when divided by n is the same. If we take n = 19, then we see that 1 is equivalent to 20, as 1/19 has a remainder of 1, and 20/19 has a remainder of 1. In fact, any number greater than 18 is equivalent to some number from 0 to 18

So x^2 = 2 (mod 19), pronounced, "x squared equivalent to 2 mod 19", means that if I take a number, square it, then it has a remainder of 2 after being divided by 19. For example, if we take x is 10, x^2 = 100, 100/19 has a remainder of 5, which of course is not equivalent to 2. So 10 is not a solution. As I said before, all the integers are equivalent to some number from 0 to 18, so these are the only numbers we must check.

Edit: Z17 has a second solution: 11^2 = 2

And as polynomials of degree two have at most 2 solutions when modded out by a prime, those are all the solutions.

Note that if x=n is a solution to x2 = 2 in Z17, x=n+17k will also be a solution for any integer k. Since x=6 and x=11 have been found to be solutions, the solution set is therefore...

Technically, yes. However, since we are in mod 17, we consider any solution that is equivalent to an already known solution to be like repeating yourself. So you don't really have to say the set, you can just say the two numbers and the rest are implied.

You aren't saying anything wrong, just unnecessary.

Ricky · 2007-02-28 11:02:16

There is no solution in Z19, Z17 has two solutions of 6 and 11.

Mathematica code for it:

Do[Print[x, ": ", PowerMod[x, 2, 19]], {x, 1, 19}]

Sekky · 2007-02-28 12:17:15

Whoops, yeah Z19 has no solutions.

JaneFairfax · 2007-02-28 13:27:44

Ricky wrote:

JaneFairfax wrote:
Note that if x=n is a solution to x2 = 2 in Z17, x=n+17k will also be a solution for any integer k. Since x=6 and x=11 have been found to be solutions, the solution set is therefore...
Technically, yes. However, since we are in mod 17, we consider any solution that is equivalent to an already known solution to be like repeating yourself. So you don't really have to say the set, you can just say the two numbers and the rest are implied.
You aren't saying anything wrong, just unnecessary.

Yeah, I was working on x[sup]2[/sup] rather than x being in

. Duh.

John E. Franklin · 2007-02-28 15:05:43

What about 13^2 is -2 from 171 (9x19) ?? Is that backwards, -2 vs. +2 ?

So 13^2 is 17 in Z19??, sort of like a negative 2 in Z19, probably not allowed to say -2, since it goes 0 to 18 for Z19, huh?

Last edited by John E. Franklin (2007-02-28 15:10:41)

JaneFairfax · 2007-02-28 15:22:40

No, +2 (mod 19) and −2 (mod 19) are different. In fact, −2 ≡ 17 (mod 19), so 13[sup]2[/sup] is 17 in

.

JaneFairfax · 2007-03-07 16:12:04

Bump.

So x[sup]2[/sup]=2 has no solution in the integers modulo 19. In other words, 2 is not a quadratic residue modulo 19, and we express this by saying

The Legendre symbol

is defined for integer a and odd prime p as follows.

It can actually be proved that

which, for p=19, gives −1.

If we had known this before, we could have saved ourselves a lot of unnecessary work.

Last edited by JaneFairfax (2007-03-07 16:50:07)

Stanley_Marsh · 2007-03-07 16:22:59

In Z17, 5^2>17 , therefore the solutions exist only above or equal to 5. Let X be the solution ,

solve this one .Oh...I forgot how to solve this equation....I am sure it can be solved.

Last edited by Stanley_Marsh (2007-03-07 16:26:08)

lightning · 2007-03-07 20:25:29

???? ????
jeez you guys are smart!

freddogtgj · 2007-03-07 23:23:38

There is no solution in Z19, Z17 has two solutions of 6 and 11.

Yea Ricky was right!

Toast · 2007-03-07 23:59:42

lightning wrote:

???? ????
jeez you guys are smart!

qft... Also Jane must make a realllly good maths teacher...

lightning · 2007-03-08 05:32:41

how is jane a maths teacher???

lightning · 2007-03-08 05:33:42

who's jane

Stanley_Marsh · 2007-03-08 10:42:46

Stanley_Marsh wrote:

In Z17, 5^2>17 , therefore the solutions exist only above or equal to 5. Let X be the solution ,
solve this one .Oh...I forgot how to solve this equation....I am sure it can be solved.

I find some information about it but I am not sure how to operate.
As I stated above , all you have to do is to solve

is equivalent to finding a value y such that

Pick a few small moduli m ,If y mod m does not make 2+17y a quadratic residue of m ,then this value of y may be excluded,Furthermore, values of y> 17/4 are never necessary.

This method is called Excludent ,by the way.

Last edited by Stanley_Marsh (2007-03-08 10:43:35)

JaneFairfax · 2009-06-16 22:30:57

[align=center]

[/align]

JaneFairfax · 2009-06-17 00:00:10

http://z8.invisionfree.com/DYK/index.php?showtopic=849

Avon · 2009-06-17 10:31:19

Jane: Using as a substitute for is just awful.

Math Is Fun Forum

#1 2007-02-28 01:34:16

help needed

#2 2007-02-28 03:16:50

Re: help needed

#3 2007-02-28 07:01:45

Re: help needed

#4 2007-02-28 07:55:53

Re: help needed

#5 2007-02-28 09:14:04

Re: help needed

#6 2007-02-28 10:56:48

Re: help needed

#7 2007-02-28 11:02:16

Re: help needed

#8 2007-02-28 12:17:15

Re: help needed

#9 2007-02-28 13:27:44

Re: help needed

#10 2007-02-28 15:05:43

Re: help needed

#11 2007-02-28 15:22:40

Re: help needed

#12 2007-03-07 16:12:04

Re: help needed

#13 2007-03-07 16:22:59

Re: help needed

#14 2007-03-07 20:25:29

Re: help needed

#15 2007-03-07 23:23:38

Re: help needed

#16 2007-03-07 23:59:42

Re: help needed

#17 2007-03-08 05:32:41

Re: help needed

#18 2007-03-08 05:33:42

Re: help needed

#19 2007-03-08 10:42:46

Re: help needed

#20 2009-06-16 22:30:57

Re: help needed

#21 2009-06-17 00:00:10

Re: help needed

#22 2009-06-17 10:31:19

Re: help needed

Board footer