• Support PF! Buy your school textbooks, materials and every day products Here!

GCD proof in Number Theory

  • Thread starter melmath
  • Start date
  • #1
1
0
Here is my problem:

Prove or disprove: If gcd(m, n) = d, then the gcd(a, mn) = gcd(a,m) * gcd(a.n)/d.

I can seem to get it started, sort of, but it just does not seem to get anywhere. I know by definition d | m and d | n. Then arbitrary integers x and y can be used such that m = xd and n = yd. I can then have gcd(a, mn) = E. Then E | a and E | mn. I can do the same as I did for the other. But the last part of gcd(a,m) * gcd(a.n)/d is giving me a really rough time getting it to know how tie it all in. I have a lot of integers and letters and I think I am very lost at this point. Please help!

melmath
 
Last edited:

Answers and Replies

  • #2
AKG
Science Advisor
Homework Helper
2,565
4
Do you know the fundamental theorem of arithmetic which says that every number can be written uniquely as a product of primes? So we can write:

[tex]m = \prod _{i=1}^{\infty}p_i^{\mu _i},\ n = \prod _{i=1}^{\infty}p_i^{\nu _i}[/tex]

where pi is the ith prime, and the [itex]\mu _i,\, \nu _i[/itex] are eventually zero since m and n are finite numbers. Using the notation above, how would you express gcd(m,n)?
 
Last edited:
  • #3
matt grime
Science Advisor
Homework Helper
9,395
3
melmath said:
Then arbitrary integers x and y can be used such that m = xd and n = yd.
x and y are not aribtrary integers. x is m/d and y is n/d.

AKG's way is very useful, but it is also good to do it from the defining characteristics: the gcd of A and B is a the largest divisor of A and B. There is also another way of thinking about it: gcd(m,n) is the integer d such that m=dx, n=dy for some x,y and gcd(x,y)=1
 

Related Threads on GCD proof in Number Theory

  • Last Post
Replies
4
Views
40K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
2
Views
430
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
404
  • Last Post
Replies
1
Views
967
Replies
2
Views
3K
  • Last Post
Replies
1
Views
1K
Replies
5
Views
499
Top