|
Show that for all positive integers a and b, we have a|b if and only if a^2|b^2:
Proof:
(1) a|b => a^2|b^2
since a|b, there exists integer k such that
b = a*k, squaring both sides:
b^2 = a^2 * k^2 , since k^2 is an integer, therefore a^2|b^2.
(2) a^2|b^2 => a|b
since a^2|b^2, there exists integer m such that
b^2 = a^2 * m ....
This is where I'm stuck, i have to show a^2|b^2 implies a|b. From the equation above, i can square root both sides, but "m" doesn't necessarily yield an integer value... does anyone have any suggestion on how i should tackle this step?
thanks in advance 
|
On October 25 2009 14:34 Mr.Maestro wrote:Show that for all positive integers a and b, we have a|b if and only if a^2|b^2: Proof: (1) a|b => a^2|b^2 since a|b, there exists integer k such that b = a*k, squaring both sides: b^2 = a^2 * k^2 , since k^2 is an integer, therefore a^2|b^2. (2) a^2|b^2 => a|b since a^2|b^2, there exists integer m such that b^2 = a^2 * m .... This is where I'm stuck, i have to show a^2|b^2 implies a|b. From the equation above, i can square root both sides, but "m" doesn't necessarily yield an integer value... does anyone have any suggestion on how i should tackle this step? thanks in advance
plz red the forum rules, ill let u off with ust a warning dont let it happen again
|
Russian Federation4235 Posts
On October 25 2009 14:36 PokePill wrote:Show nested quote +On October 25 2009 14:34 Mr.Maestro wrote:Show that for all positive integers a and b, we have a|b if and only if a^2|b^2: Proof: (1) a|b => a^2|b^2 since a|b, there exists integer k such that b = a*k, squaring both sides: b^2 = a^2 * k^2 , since k^2 is an integer, therefore a^2|b^2. (2) a^2|b^2 => a|b since a^2|b^2, there exists integer m such that b^2 = a^2 * m .... This is where I'm stuck, i have to show a^2|b^2 implies a|b. From the equation above, i can square root both sides, but "m" doesn't necessarily yield an integer value... does anyone have any suggestion on how i should tackle this step? thanks in advance plz red the forum rules, ill let u off with ust a warning dont let it happen again
Please read the forum rules, I'll let you off with just a warning for now, but don't let it happen again/
|
Write a and b in unique factorization, and the proof is obvious. Basically you cannot get new factors by squaring.
|
On October 25 2009 14:36 PokePill wrote:Show nested quote +On October 25 2009 14:34 Mr.Maestro wrote:Show that for all positive integers a and b, we have a|b if and only if a^2|b^2: Proof: (1) a|b => a^2|b^2 since a|b, there exists integer k such that b = a*k, squaring both sides: b^2 = a^2 * k^2 , since k^2 is an integer, therefore a^2|b^2. (2) a^2|b^2 => a|b since a^2|b^2, there exists integer m such that b^2 = a^2 * m .... This is where I'm stuck, i have to show a^2|b^2 implies a|b. From the equation above, i can square root both sides, but "m" doesn't necessarily yield an integer value... does anyone have any suggestion on how i should tackle this step? thanks in advance plz red the forum rules, ill let u off with ust a warning dont let it happen again
He didn't ask us to do his homework. He was just asking for help. At least he is actually trying to do it. Another thing, you're not staff.
|
On October 25 2009 14:36 PokePill wrote:Show nested quote +On October 25 2009 14:34 Mr.Maestro wrote:Show that for all positive integers a and b, we have a|b if and only if a^2|b^2: Proof: (1) a|b => a^2|b^2 since a|b, there exists integer k such that b = a*k, squaring both sides: b^2 = a^2 * k^2 , since k^2 is an integer, therefore a^2|b^2. (2) a^2|b^2 => a|b since a^2|b^2, there exists integer m such that b^2 = a^2 * m .... This is where I'm stuck, i have to show a^2|b^2 implies a|b. From the equation above, i can square root both sides, but "m" doesn't necessarily yield an integer value... does anyone have any suggestion on how i should tackle this step? thanks in advance plz red the forum rules, ill let u off with ust a warning dont let it happen again
How am i violating the forum rules? I posted a homework question and i made a sincere effort of my own to attempt to solve it. I'm just asking for some clarification on how I should carry out a step in my solution. How is that wrong?
|
United States4796 Posts
On October 25 2009 14:47 Mr.Maestro wrote:Show nested quote +On October 25 2009 14:36 PokePill wrote:On October 25 2009 14:34 Mr.Maestro wrote:Show that for all positive integers a and b, we have a|b if and only if a^2|b^2: Proof: (1) a|b => a^2|b^2 since a|b, there exists integer k such that b = a*k, squaring both sides: b^2 = a^2 * k^2 , since k^2 is an integer, therefore a^2|b^2. (2) a^2|b^2 => a|b since a^2|b^2, there exists integer m such that b^2 = a^2 * m .... This is where I'm stuck, i have to show a^2|b^2 implies a|b. From the equation above, i can square root both sides, but "m" doesn't necessarily yield an integer value... does anyone have any suggestion on how i should tackle this step? thanks in advance plz red the forum rules, ill let u off with ust a warning dont let it happen again How am i violating the forum rules? I posted a homework question and i made a sincere effort of my own to attempt to solve it. I'm just asking for some clarification on how I should carry out a step in my solution. How is that wrong?
You aren't. Don't worry. PokePill is not an admin here.
What is the definition of a|b? Which math is this? I may be able to help you if I know which math this is, haha.
|
As illu said, all you gotta do is write the unique factorizations of a and b, and notice that squaring doesn't add different prime factors.
|
Bisutopia19345 Posts
|
its algebra, a divides b
sorry though, don't really remember it too much right now
|
One approach is to divide by a^2 and take the square root. Then sqrt(m) = b/a, b and a both integers.
What do you know about the relationship between square roots and rational numbers?
...though, perhaps this hasn't come up in your class yet. Sorry if that's the case.
|
prime factorizationnnnnnnnnnnnnnnnnn
|
Kentor
United States5784 Posts
On October 25 2009 15:25 Day[9] wrote:
prime factorizationnnnnnnnnnnnnnnnnn
math gosu
|
How directly can you use prime factorization?
The minimal solution I could find was for primes p
Use p|bc => p|b or p|c if you can (except I can't prove this without directly applying prime factorization...)
Consider minimal elements p[i] s.t. p[i] | a, but ! p[i] | b and there is no p[j] s.t. p[j] | p[i] (use well-ordered principle, basically establishing prime divisors)
p[i]^2 | b*b => p[i] | b*b => p[i] | b, contradiction.
Maybe there's a horrible way to do this by applying WOP to avoid prime factorization.
|
as above but in more colloquial terms:
assume a^2 | b^2, suppose a does not divide b, (a|/b). a^2 = b * b * m for some integer m. Therefore a^2 | b => a*a | b. Therefore using prime factorization, either a divides b or a divides b. contradiction since we assumed a|/ b. therefore a^2 | b^2 = > a|b
|
Recheck your notation and your argument...
|
On October 25 2009 14:34 Mr.Maestro wrote:Show that for all positive integers a and b, we have a|b if and only if a^2|b^2: Proof: (1) a|b => a^2|b^2 since a|b, there exists integer k such that b = a*k, squaring both sides: b^2 = a^2 * k^2 , since k^2 is an integer, therefore a^2|b^2. (2) a^2|b^2 => a|b since a^2|b^2, there exists integer m such that b^2 = a^2 * m .... This is where I'm stuck, i have to show a^2|b^2 implies a|b. From the equation above, i can square root both sides, but "m" doesn't necessarily yield an integer value... does anyone have any suggestion on how i should tackle this step? thanks in advance
Let's try contrapositive
a^2 | b^2 => a | b
is the same as
a not | b => a^2 not | b^2
if a does not divide b, we can apply the division algorithm, saying b = quotient * divisor + remainder,
or
b = p*a + r where p can be anything and r =/= 0, r < a (1)
then b^2 = p^2 * a ^2 + 2 * p*a * r + r^2 = stuff*a + r^2
if a^2 divides b^2, then r^2 = 0, which it cannot, or r^2 = a*a*shit
r^2 = a*shit = a*a*shit_1*shit_1
then r = a*shit_1
which causes a contradiction since (1) states r<a
haha fuck the argument doesn't work lolol
i thought i was being slick by doing (a*p + r)^2 hahaha
|
But contradiction is still the way to go.
a does not divide b, that means if we factor both a and b, we will get
a = p1*p2*...*ps
b = q1*q2*...*qt
if a does not divide b, that means {p1,...,ps} is not contained in {q1,...,qt}
(in the case a>b it's pretty simple, a^2>b^2 then clearly it doesn't divide as well)
in particular, there is a pi that is a factor of a that's not a factor of b
then a^2 = p1^2 * ... * pn^2
and b^2 = q1^2 * ... * qn^2
and we see that pi is still in a^2 and pi is not a factor of b^2
|
I assume this isnt a cyclic group of integers?
Either way if A doesnt divide B then A != B*m => A^2 != B^2m^2 And we have resulted in a contradiction since the question states that A^2 = B^2*N where n = M^2
Gotta be careful with logic here, since we have just disproved that A !=B*m (the implication of the first part is false) and this is equivelant to A divides B, and then there is an axiom you can use (i think it is the fundamental theorem of number theory) that allows you to show the only other case is A = B*m
|
|
|
|
|
|
EPT
