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

  • Thread starter Thread starter rerouter
  • Start date Start date
  • Tags Tags
    Divisibility
rerouter
Messages
9
Reaction score
0

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.
 
Physics news on Phys.org
welcome to pf!

hi rerouter! welcome to pf! :smile:

(try using the X2 icon just above the Reply box :wink:)

hint: always try the easy case first …

prove it for n = m2, then fiddle about a bit :wink:
 
Thanks for the welcome tiny-tim, I appreciate it!

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

An example:

a2=n2m
b2=n2k

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

a2b=n2mb
b2a=n2ka

Adding them:

a2b + b2a=n2mb + n2ka
ab(a+b)=n2(mb+ka)

Since I can't divide by (a+b) to show that ab is a multiple of n2, 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.
 
hmm …

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

let n = m2

if m2 | a2, what can you say about m ?​
 
Hmmm... m<=a ?
 
how about m | a ? :smile:
 
While I see that that's true...I'm not sure how to show that.

Given:

m2|a2

a2=m2k (...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?
 
Forgive me for being dense, lol.
 
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?
 
  • #10
I think then: a and b would then each have at least k factors of p in them.
 
Last edited:
  • #11
rerouter said:
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.
 
  • #12
If I consider n=pks

and n|a2

then

a2=nt
a2=pkst

It looks like

a=sqrt(pkst)
a=pk/2sqrt(st)

so that is k/2 p's ?
 
  • #13
rerouter said:
If I consider n=pks

and n|a2

then

a2=nt
a2=pkst

It looks like

a=sqrt(pkst)
a=pk/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.
 
Last edited:
  • #14
Maybe.

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

a2=pjs, p, j, and s primes.
b2=pjr, p, j, and r primes.

n|a2 means that

a2=nw
a2=pjv

n|b2 means that

b2=nx
b2=pjy


Since

a=(pj)k(pj)1/2x1/2
b=(pj)k(pj)1/2y1/2


a and b are multiples of pj, so n|ab ?
 
  • #15
rerouter said:
Maybe.

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

a2=pjs, p, j, and s primes.
b2=pjr, p, j, and r primes.

n|a2 means that

a2=nw
a2=pjv

n|b2 means that

b2=nx
b2=pjySince

a=(pj)k(pj)1/2x1/2
b=(pj)k(pj)1/2y1/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??
 
  • #16
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|a2 and n|b2, we know that.

a2=(pj)s
b2=(pj)r

s,r some integers, not necessarily prime.

So

a2*b2=(pj)s(pj)r
a2*b2=(pj)2sr

so..

ab=pj*sqrt(sr)

In this case, n has pk as a factor with k=1 and ab has pk 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 pk as a factor, and ab has pk as a factor, then ab is a multiple of pk. Is that the idea?
 
  • #17
rerouter said:
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|a2 and n|b2, we know that.

a2=(pj)s
b2=(pj)r

s,r some integers, not necessarily prime.

So

a2*b2=(pj)s(pj)r
a2*b2=(pj)2sr

so..

ab=pj*sqrt(sr)

In this case, n has pk as a factor with k=1 and ab has pk 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 pk as a factor, and ab has pk as a factor, then ab is a multiple of pk. 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.
 
Back
Top