Proving n & m Divide k When gcd(m,n)=1

  • Context: Undergrad 
  • Thread starter Thread starter Diophantus
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around proving that if two natural numbers \( m \) and \( n \) are coprime (i.e., \( \text{gcd}(m,n) = 1 \)) and both divide a natural number \( k \), then their product \( nm \) also divides \( k \). The scope includes mathematical reasoning and exploration of number theory concepts.

Discussion Character

  • Exploratory
  • Mathematical reasoning

Main Points Raised

  • One participant requests assistance in recalling how to prove that \( nm | k \) given \( n | k \) and \( m | k \).
  • Another participant suggests considering the implications of \( n | k \) and \( m | k \) in terms of mathematical symbols and applying the gcd condition.
  • A third participant mentions the relevance of the fundamental theorem of arithmetic to the problem.
  • A later reply proposes decomposing \( m \) and \( n \) into their unique prime factors, noting that since they are coprime, their prime factors do not overlap, leading to the conclusion that \( nm | k \).

Areas of Agreement / Disagreement

Participants do not express disagreement, but the discussion reflects a progression of understanding rather than a consensus on a formal proof.

Contextual Notes

The discussion relies on the properties of prime factorization and the definition of coprimality, which may not be explicitly detailed in the posts.

Diophantus
Messages
69
Reaction score
0
I forgot how to prove the following, can anyone jog my memory:

Let m,n be natural numbers s.t. gcd(m,n) = 1 and n|k and m|k for some natural number k.

Then nm|k.

I know I'll kick myself when I find out. Thanks.
 
Physics news on Phys.org
well what do n|k and m|k represent and what does it imply about k? think in terms of mathematical symbols and not words. Apply the gcd constriction and then you should be done.
 
This also falls to the fundamental theorem of arithmetic nicely.
 
Oh I see it now!

You just decompose m and n into their unique prime factors and note that no prime factor of m can be a prime factor of n and vice versa.

So if am = k = bn then each prime factor of n, say, divides a (with aprropriate multiplicity) and hence n divides a giving the result.

Ta.
 

Similar threads

  • · Replies 3 ·
Replies
3
Views
3K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 25 ·
Replies
25
Views
4K
  • · Replies 4 ·
Replies
4
Views
3K
  • · Replies 3 ·
Replies
3
Views
1K
Replies
8
Views
5K
  • · Replies 40 ·
2
Replies
40
Views
4K
Replies
12
Views
4K
  • · Replies 8 ·
Replies
8
Views
3K