Perfect square

• Apr 8th 2010, 09:55 PM
kingwinner
Perfect square
1) If gcd(x,3)=1 and gcd(y,3)=1, prove that $x^2 + y^2$ cannot be a perfect square.

2) Given that gcd(a,b,c)lcm(a,b,c) = abc, prove that gcd(a,b)=gcd(b,c)=gcd(a,c)=1.

This is not homework, I'm doing it for extra practice, but I can't figure out how to prove these.

Any help would be appreciated!

[also under discussion in math link forum]
• Apr 8th 2010, 10:28 PM
chiph588@
Quote:

Originally Posted by kingwinner
1) If gcd(x,3)=1 and gcd(y,3)=1, prove that $x^2 + y^2$ cannot be a perfect square.

$(x,3)=1\implies x\equiv\pm1\bmod{3}$

Therefore $x^2+y^2\equiv1+1=2\bmod{3}$.

So if $x^2+y^2=z^2 \implies z^2\equiv 2\bmod{3}$, which is impossible.
• Apr 9th 2010, 03:04 PM
FancyMouse
Quote:

Originally Posted by kingwinner
2) Given that gcd(a,b,c)lcm(a,b,c) = abc, prove that gcd(a,b)=gcd(b,c)=gcd(a,c)=1.

Fix a prime p, suppose the exponent of a,b,c of p are x,y,z respectively, WLOG suppose a<=b<=c. Show a=b=1
• Apr 9th 2010, 05:20 PM
kingwinner
Quote:

Originally Posted by FancyMouse
Fix a prime p, suppose the exponent of a,b,c of p are x,y,z respectively, WLOG suppose a<=b<=c. Show a=b=1

Q2) I've thought about it for awhile, but I can't figure out how to show a=b=1.

Also, aren't we supposed to show gcd(a,b)=gcd(b,c)=gcd(a,c)=1. How can we prove this?

Thanks!
• Apr 9th 2010, 05:24 PM
kingwinner
Quote:

Originally Posted by chiph588@
$(x,3)=1\implies x\equiv\pm1\bmod{3}$

Therefore $x^2+y^2\equiv1+1=2\bmod{3}$.

So if $x^2+y^2=z^2 \implies z^2\equiv 2\bmod{3}$, which is impossible.

Thanks!
"If x and y are odd, prove that $x^2 + y^2$ cannot be a perfect square."

x odd => x=1(mod2) => $x^2$ = 1 (mod 2)
=> $x^2 + y^2$ = 0 (mod 2)
=> ???
• Apr 9th 2010, 05:37 PM
chiph588@
Quote:

Originally Posted by kingwinner
Thanks!
"If x and y are odd, prove that $x^2 + y^2$ cannot be a perfect square."

x odd => x=1(mod2) => $x^2$ = 1 (mod 2)
=> $x^2 + y^2$ = 0 (mod 2)
=> ???

$(x,3)=1\not\Longrightarrow x$ is odd. For example, $(4,3)=1$.
• Apr 9th 2010, 06:04 PM
kingwinner
Quote:

Originally Posted by chiph588@
$(x,3)=1\not\Longrightarrow x$ is odd. For example, $(4,3)=1$.

Sorry, maybe I wasn't clear. This is a different problem.
"If x and y are odd, prove that $x^2 + y^2$ cannot be a perfect square."
How can we prove this?
• Apr 9th 2010, 06:10 PM
chiph588@
Quote:

Originally Posted by kingwinner
Sorry, maybe I wasn't clear. This is a different problem.
"If x and y are odd, prove that $x^2 + y^2$ cannot be a perfect square."
How can we prove this?

Look at the definition of a Pythagorean triple (not necessarily primitive). One term is always a multiple of $2$.
• Apr 9th 2010, 06:34 PM
kingwinner
Quote:

Originally Posted by chiph588@
Look at the definition of a Pythagorean triple (not necessarily primitive). One term is always a multiple of $2$.

""If x and y are odd, prove that http://www.mathhelpforum.com/math-he...e756abff-1.gif cannot be a perfect square."

How can we prove this directly by basic modular arithmetic?

x odd => x=1(mod2) => $x^2$ = 1 (mod 2)
=> $x^2 + y^2$ = 0 (mod 2)
But I can't find a contradiction here...
• Apr 9th 2010, 06:43 PM
chiph588@
Quote:

Originally Posted by kingwinner
""If x and y are odd, prove that http://www.mathhelpforum.com/math-he...e756abff-1.gif cannot be a perfect square."

How can we prove this directly by basic modular arithmetic?

x odd => x=1(mod2) => $x^2$ = 1 (mod 2)
=> $x^2 + y^2$ = 0 (mod 2)
But I can't find a contradiction here...

This isn't a contradiction since $z^2\equiv0\bmod{2}$ is solvable.
• Apr 9th 2010, 08:50 PM
kingwinner
Quote:

Originally Posted by chiph588@
Look at the definition of a Pythagorean triple (not necessarily primitive). One term is always a multiple of $2$.

So how can we prove this claim?
(this question is from the section on basic modular arithmetic; Pythagroean triple hasn't been introduced yet so I don't think we'll need it)

Thanks!
• Apr 9th 2010, 09:08 PM
Drexel28
Quote:

Originally Posted by kingwinner
So how can we prove this claim?
(this question is from the section on basic modular arithmetic; Pythagroean triple hasn't been introduced yet so I don't think we'll need it)

Thanks!

Why can't you just note that if $x=2n+1,y=2m+1$ then $x^2+y^2=4n^2+4n+1+4m^2+4m+1\equiv2\text{ mod }4$ but the reduced residue class of $x^2\text{ mod }4$ is $\{0,1\}$?
• Apr 10th 2010, 01:44 PM
kingwinner
Thanks! How to prove Q2?
2) Given that gcd(a,b,c)lcm(a,b,c) = abc, prove that gcd(a,b)=gcd(b,c)=gcd(a,c)=1.
• Apr 10th 2010, 01:57 PM
FancyMouse
Quote:

Originally Posted by kingwinner
Q2) I've thought about it for awhile, but I can't figure out how to show a=b=1.

Also, aren't we supposed to show gcd(a,b)=gcd(b,c)=gcd(a,c)=1. How can we prove this?

Thanks!

Sorry there's a typo. I meant x=y=1, not a=b=1. i.e. if p^x || a (i.e. p^x divides a but p^{x+1} doesn't divide a), p^y || b, p^z || c, and x<=y<=z, then x=y=1, which implies that if some prime one of a,b,c is divisible by p, then only one of them is divisible by p