Author |
Topic: Odd prime not dividing a product (Read 4356 times) |
|
Michael Dagg
Senior Riddler
Gender: 
Posts: 500
|
 |
Odd prime not dividing a product
« on: Nov 29th, 2011, 7:08pm » |
 Quote  Modify
|
Suppose p is an odd prime not dividing ab . Prove that
z^2 = ab (mod p)
is solvable exactly when both or neither
x^2 = a (mod p) and y^2 = b (mod p) are solvable.
|
|
 IP Logged |
Regards,
Michael Dagg
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Odd prime not dividing a product
« Reply #1 on: Dec 3rd, 2011, 2:04pm » |
Quote Modify
|
If z2 = ab (mod p) and x2 = a (mod p) have solutions, then we can find y2 = (z/x)2 = b (mod p)
So if z2 = ab (mod p) is solvable, either both or neither x2 = a (mod p) and y2 = b (mod p) are solvable
If both x2 = a (mod p) and y2 = b (mod p) are solvable, then trivially z2 = x2y2 = ab (mod p) is solvable.
If neither x2 = a (mod p) nor y2 = b (mod p), then x2 = -a (mod p) and y2 = -b (mod p) are solvable and therefor z2 = x2y2 = (-a)(-b) (mod p) = ab (mod p) is solvable.
Although I suppose I ought to also prove that for 0 < k < p either k or -k is a square (mod p), and not just go on my hunch that that is the case.
Not quite there yet...
|
| « Last Edit: Dec 4th, 2011, 10:34am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Odd prime not dividing a product
« Reply #2 on: Dec 4th, 2011, 7:38am » |
Quote Modify
|
on Dec 3rd, 2011, 2:04pm, towr wrote:Although I suppose I ought to also prove that for 0 < k < p either k or -k is a square (mod p), and not just go on my hunch that that is the case.
Not quite there yet... |
|
When p=5, the squares are 1 and -1...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Odd prime not dividing a product
« Reply #3 on: Dec 4th, 2011, 10:30am » |
Quote Modify
|
Well, damn. Why can't reality just conform to my delusions and makes things easier 
On the bright side it absolves me having to try and prove it.
|
| « Last Edit: Dec 4th, 2011, 10:32am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
peoplepower
Junior Member
Posts: 63
|
|
Re: Odd prime not dividing a product
« Reply #4 on: Jul 31st, 2012, 8:20am » |
Quote Modify
|
Let f be a homomorphism from the multiplicative group of integers mod p to itself given by the power map f(x)=x2. The image of f is the (group G) of squares, i.e. the collection of all elements a such that x2=a(mod p) is solvable. The properties of groups verify all of the implications asked except for that if a and b are neither elements of G then ab is an element of G. Suppose c generates the cyclic group (Z/pZ)x. Then, f(cn)=c2n; i.e. x is an element of G iff the power of x is divisible by 2. There exists smallest positive integers m,n such that cm=a and cn=b. Since a and b are not in G, m and n must be odd. Now, ab= cm+n has even power.
|
| « Last Edit: Jul 31st, 2012, 8:47am by peoplepower » |
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Odd prime not dividing a product
« Reply #5 on: Aug 7th, 2012, 3:20pm » |
Quote Modify
|
I am not too fond of the phrase "The properties of groups verify
all of the implications asked for..."
This may provide better clarity:
Let G be the multiplicative group of all nonzero congruence
classes in Z/pZ . Define a function f: G-> G by f(x) = x^2 .
Since Z/pZ is a domain, the product of nonzero elements is nonzero,
and so x \neq 0 implies x^2 \neq 0; that is, f \subseteq G .
Next, f is a homomorphism, because
f(xy) = (xy)^2 = x^2y^2 = f(x)f(y)
(the second equality holding because G is commutative). Finally,
f is an isomorphism: since p is odd, gcd(2, p) = 1 , and there
are integers s and t with 2s + pt = 1 . The inverse of f is g ,
where g(x) = x^s . Therefore, f is surjective; that is, every
element of G is a square.
There is one step left and I will let you take it.
Notice that the fact that G is cyclic is not needed.
|
|
IP Logged |
Regards,
Michael Dagg
|
|
|
peoplepower
Junior Member
Posts: 63
|
|
Re: Odd prime not dividing a product
« Reply #6 on: Aug 11th, 2012, 9:38pm » |
Quote Modify
|
Well, given s and t as you constructed,
g(f(x))=x2s=x*(x-1)pt.
For any y, if ypt=1, then yt=1 since yp=y*y (p).
Thus, -1, with period 2, is a counterexample to the proposition g(f(x))=x.
|
| « Last Edit: Aug 11th, 2012, 9:38pm by peoplepower » |
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Odd prime not dividing a product
« Reply #7 on: Aug 12th, 2012, 9:41am » |
Quote Modify
|
You're right. I was thinking of G as Z/pZ but, of course, it isn't.
(This would have implied x^p = 1 for x in G, whereas we really have
px = 0). In fact, |G| = p - 1, which is even, and so squaring is
not an automorphism of G.
I think it is fair to say welcome back.
|
| « Last Edit: Aug 12th, 2012, 9:43am by Michael Dagg » |
IP Logged |
Regards,
Michael Dagg
|
|
|
peoplepower
Junior Member
Posts: 63
|
|
Re: Odd prime not dividing a product
« Reply #8 on: Sep 10th, 2012, 5:21pm » |
Quote Modify
|
You are right that the group being cyclic is unnecessary.
Theorem Let H be a subgroup of index 2 of a finite group G.
(1) If a,b are in H, then ab is in H.
(2) If a,b are not in H, then ab is in H.
(3) If exactly one of a,b is in H, then ab is not in H.
Proof 2 is the smallest prime dividing |G|, so |G:H|=2 implies H is a normal subgroup of G. Therefore, G/H is a group with two elements. In particular, G/H is cyclic generated by gH of order 2 (for some g in G).
(1) By hypothesis, H is a subgroup and therefore is closed.
(2) a and b are in the same nonidentity coset of H. Then, ab is a member of the product gHgH in G/H. But, gHgH=ggHH=H.
(3) abH=aHbH=gHH=gH, the second equality is due to G/H being abelian.
Corollary Let p be an odd prime number.
For any elements a,b in (Z/pZ)x:
(1) If a,b are both squares, then ab is a square.
(2) If neither a nor b is a square, then ab is a square.
(3) If exactly one of a,b is a square, then ab is not a square.
Proof Let G=(Z/pZ)x. Define f:G G by f(x)=x2. Since f(xy)=xyxy=x2y2, f is a group homomorphism, so its image H=f(G) is a subgroup of G. Clearly, H contains all squares and nothing else. Thus, all that is left before applying the theorem is to prove that the index of H is 2, that is, the kernel has to have exactly two elements.
Suppose n2=1(mod p), then (n-1)(n+1)=0, so either n-1=0 or n+1=0; that is n= 1(mod p). Since p>2, -1 and +1 are the distinct of the elements of the kernel.
|
| « Last Edit: Sep 11th, 2012, 5:22am by peoplepower » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print