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

In summary, the homework statement is trying to find a way to show that ab=n(something), but can't for the life of me find a way to show this.
  • #1
rerouter
9
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
  • #2
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:
 
  • #3
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.
 
  • #4
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 ?​
 
  • #5
Hmmm... m<=a ?
 
  • #6
how about m | a ? :smile:
 
  • #7
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?
 
  • #8
Forgive me for being dense, lol.
 
  • #9
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.
 

1. What is the "Simple Divisibility Problem"?

The Simple Divisibility Problem is a mathematical concept that states that if a number, n, divides into the square of one number, a^2, and the square of another number, b^2, then it must also divide into the product of those two numbers, ab.

2. What is the significance of proving the Simple Divisibility Problem?

Proving the Simple Divisibility Problem is important in mathematics because it is a fundamental concept that is used in many other mathematical proofs and theorems. It also helps in solving more complex divisibility problems and understanding the relationship between different numbers.

3. Why is it important to have n as the common factor in all three numbers?

Having n as the common factor in all three numbers is important because it is the key element in proving the Simple Divisibility Problem. It shows that n is a factor of both a and b, and therefore must also be a factor of their product, ab.

4. Can the Simple Divisibility Problem be proved using other methods?

Yes, there are multiple ways to prove the Simple Divisibility Problem. Some common methods include using the Euclidean algorithm, mathematical induction, and proof by contradiction. However, the most straightforward and commonly used method is the direct proof.

5. How is the Simple Divisibility Problem applied in real-life situations?

The Simple Divisibility Problem has various applications in real-life situations. For example, it is used in cryptography, coding theory, and computer science to ensure that data is transmitted and stored accurately. It is also used in engineering and physics to solve problems involving forces and motion.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
451
  • Calculus and Beyond Homework Help
Replies
1
Views
457
  • Calculus and Beyond Homework Help
Replies
3
Views
467
  • Precalculus Mathematics Homework Help
Replies
3
Views
754
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
600
  • Calculus and Beyond Homework Help
Replies
5
Views
5K
  • Calculus and Beyond Homework Help
Replies
18
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
842
Back
Top