wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Odd prime not dividing a product
        
(Message started by: Michael Dagg on Nov 29^th, 2011, 7:08pm)

Title: Odd prime not dividing a product
Post by Michael Dagg on Nov 29^th, 2011, 7:08pm

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.

Title: Re: Odd prime not dividing a product
Post by towr on Dec 3^rd, 2011, 2:04pm

[hide]If z² = ab (mod p) and x² = a (mod p) have solutions, then we can find y² = (z/x)² = b (mod p)
So if z² = ab (mod p) is solvable, either both or neither x² = a (mod p) and y² = b (mod p) are solvable

If both x² = a (mod p) and y² = b (mod p) are solvable, then trivially z² = x²y² = ab (mod p) is solvable.
If neither x² = a (mod p) nor y² = b (mod p), then x² = -a (mod p) and y² = -b (mod p) are solvable and therefor z² = x²y² = (-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...[/hide]

Title: Re: Odd prime not dividing a product
Post by rmsgrey on Dec 4^th, 2011, 7:38am

on 12/03/11 at 14:04:03, 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...

Title: Re: Odd prime not dividing a product
Post by towr on Dec 4^th, 2011, 10:30am

Well, damn. Why can't reality just conform to my delusions and makes things easier :P
On the bright side it absolves me having to try and prove it.

Title: Re: Odd prime not dividing a product
Post by peoplepower on Jul 31^st, 2012, 8:20am

Let f be a homomorphism from the multiplicative group of integers mod p to itself given by the power map f(x)=x². The image of f is the (group G) of squares, i.e. the collection of all elements a such that x²=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(cⁿ)=c²ⁿ; 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 c^m=a and cⁿ=b. Since a and b are not in G, m and n must be odd. Now, ab= c^m+n has even power.

Title: Re: Odd prime not dividing a product
Post by Michael Dagg on Aug 7^th, 2012, 3:20pm

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.

Title: Re: Odd prime not dividing a product
Post by peoplepower on Aug 11^th, 2012, 9:38pm

Well, given s and t as you constructed,
g(f(x))=x^2s=x*(x^-1)^pt.
For any y, if y^pt=1, then y^t=1 since y^p=y*y^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(p)}.
Thus, -1, with period 2, is a counterexample to the proposition g(f(x))=x.

Title: Re: Odd prime not dividing a product
Post by Michael Dagg on Aug 12^th, 2012, 9:41am

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.

Title: Re: Odd prime not dividing a product
Post by peoplepower on Sep 10^th, 2012, 5:21pm

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:Ghttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifG by f(x)=x². Since f(xy)=xyxy=x²y², 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 n²=1(mod p), then (n-1)(n+1)=0, so either n-1=0 or n+1=0; that is n=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1(mod p). Since p>2, -1 and +1 are the distinct of the elements of the kernel.