Proving the Simple Divisibility Problem | n|a^2 & n|b^2 implies n|ab

[rerouter]

Homework Statement

Question: If n|a^2 and n|b^2 prove or disprove that n|ab.

I think this is true, but am having trouble proving it.

Homework Equations

a^2=nm, b^2=nk

a^2-b^2=n(m-k)
a^2+b^2=n(m+k)

The Attempt at a Solution

Essentially I've tried all sorts of algebraic ways to show that ab=n(something), but can't for the life of me find a way to show this. I must be missing something embarassingly obvious.

Any hints appreciated.

 

[tiny-tim]

welcome to pf!

hi rerouter! welcome to pf!

(try using the X² icon just above the Reply box )

hint: always try the easy case first …

prove it for n = m², then fiddle about a bit

 

[rerouter]

Thanks for the welcome tiny-tim, I appreciate it!

I just looked at it again using n² instead of n. I still have the problem that I can't seem to isolate ab.

An example:

a²=n²m
b²=n²k

Lets say I multipy those by b and a respectively, to try and get some ab's.

a²b=n²mb
b²a=n²ka

Adding them:

a²b + b²a=n²mb + n²ka
ab(a+b)=n²(mb+ka)

Since I can't divide by (a+b) to show that ab is a multiple of n², in case (a+b) is 0. I'm sort of stuck. I've basically been trying similar manipulations to this, but end up in a case where I can't isolate ab, as above. Which leads me to believe I'm missing something pretty fundamental, lol.

 

[tiny-tim]

hmm …

you're making this complicated by using the same letter for n as for √n

let n = m² …

if m² | a², what can you say about m ?​

 

[rerouter]

Hmmm... m<=a ?

 

[tiny-tim]

how about m | a ?

 

[rerouter]

While I see that that's true...I'm not sure how to show that.

Given:

m²|a²

a²=m²k (...k some integer)

so..

a=m*sqrt(k)

Showing that a is a multiple of m, thus m|a. But how can I justify this? What if sqrt(k) is not an interger. I know from a few trials, that k either equals 1, or is itself a sqaure, but I think that would need to be proven would it not?

 

[rerouter]

Forgive me for being dense, lol.

 

[Dick]

I think you want to start counting prime factors here. If p^k is the largest power of the prime p that divides n, at least how many factors of p do a and b have?

 

[rerouter]

I think then: a and b would then each have at least k factors of p in them.

 

[Dick]

I think then: a and b would then each have at least k factors of p in them.

If n|a^2, then I would say 'a' should have at least k/2 factors of p. Do you see why? 9|3^2. But 3 doesn't have two factors of 3.

 

[rerouter]

If I consider n=p^ks

and n|a²

then

a²=nt
a²=p^kst

It looks like

a=sqrt(p^kst)
a=p^k/2sqrt(st)

so that is k/2 p's ?

 

[Dick]

If I consider n=p^ks

and n|a²

then

a²=nt
a²=p^kst

It looks like

a=sqrt(p^kst)
a=p^k/2sqrt(st)

so that is k/2 p's ?

Sort of. Except that k might not be divisible by 2. But that doesn't matter. If n has k factors of p then a^2 must also have at least k factors of p. What I really wanted you to say is "I know about primes and unique factorization". It's probably easier to say that in words than write the formula. Do you see how the rest of it works? I'm more interested in whether you get the concept than how you would write it out.

 

[rerouter]

Maybe.

So let's say n=pj, p and j are primes.

a²=pjs, p, j, and s primes.
b²=pjr, p, j, and r primes.

n|a² means that

a²=nw
a²=pjv

n|b² means that

b²=nx
b²=pjy


Since

a=(pj)^k(pj)^1/2x^1/2
b=(pj)^k(pj)^1/2y^1/2


a and b are multiples of pj, so n|ab ?

 

[Dick]

Maybe.

So let's say n=pj, p and j are primes.

a²=pjs, p, j, and s primes.
b²=pjr, p, j, and r primes.

n|a² means that

a²=nw
a²=pjv

n|b² means that

b²=nx
b²=pjySince

a=(pj)^k(pj)^1/2x^1/2
b=(pj)^k(pj)^1/2y^1/2a and b are multiples of pj, so n|ab ?

Mmm. I think you might have been staring at this problem too long. That's not making a lot of sense. The idea here (in words) is to consider the prime factorization of n. If p is any prime factor of n and p^k is the largest power of p dividing n, then you need to show ab has at least k factors of p. Wouldn't that do the job of proving it??

 

[rerouter]

Yes, I think that makes sense. I thought that is what I had shown, "sort of", lol. For some reason I think I wrote the same thing twice with different variables.

So let's say n=pj, p and j are primes. (This is the prime factorization of n). Since n|a² and n|b², we know that.

a²=(pj)s
b²=(pj)r

s,r some integers, not necessarily prime.

So

a²*b²=(pj)s(pj)r
a²*b²=(pj)²sr

so..

ab=pj*sqrt(sr)

In this case, n has p^k as a factor with k=1 and ab has p^k with k=1. So ab has k=1 factors of p. Is that right?

I think I get the idea of what you are saying. To paraphrase:

If n has p^k as a factor, and ab has p^k as a factor, then ab is a multiple of p^k. Is that the idea?

 

[Dick]

Yes, I think that makes sense. I thought that is what I had shown, "sort of", lol. For some reason I think I wrote the same thing twice with different variables.

So let's say n=pj, p and j are primes. (This is the prime factorization of n). Since n|a² and n|b², we know that.

a²=(pj)s
b²=(pj)r

s,r some integers, not necessarily prime.

So

a²*b²=(pj)s(pj)r
a²*b²=(pj)²sr

so..

ab=pj*sqrt(sr)

In this case, n has p^k as a factor with k=1 and ab has p^k with k=1. So ab has k=1 factors of p. Is that right?

I think I get the idea of what you are saying. To paraphrase:

If n has p^k as a factor, and ab has p^k as a factor, then ab is a multiple of p^k. Is that the idea?

No, you've garbled the paraphrase. If p^k is the largest power of p that divides n, and you can show p^k also divides ab, for ALL prime factors of n, then n divides ab. I really think you should take another look at this in the morning. Get some sleep and think about prime factorization.