Help : greatest common factor

  • Thread starter xuying1209
  • Start date
However, if we assume that there exists a specific s and t that satisfy the given conditions, then the statement is true. To prove it, we can use the fact that gcd(n,m)=1 to show that the gcd of z and nm is equal to the product of d_n and d_m. This can be done by expressing z as a linear combination of n and m using the given equations and then using the properties of gcd.
  • #1
xuying1209
4
0
For any n,m are intergers, d_n and d_m are divisors of n and m,
respectively. If gcd(n,m)=1, gcd(i,n)=d_n , gcd(j,m)=d_m
sm=1(mod n) , tn=1(mod m),
z=smi+tnj (mod nm)
then gcd(z,nm)=d_nd_m.
I want to know the result is true or false, and how to prove it.

Thanks. :smile:
 
Physics news on Phys.org
  • #2
xuying1209 said:
For any n,m are intergers, d_n and d_m are divisors of n and m,
respectively. If gcd(n,m)=1, gcd(i,n)=d_n , gcd(j,m)=d_m
sm=1(mod n) , tn=1(mod m),
z=smi+tnj (mod nm)
then gcd(z,nm)=d_nd_m.
I want to know the result is true or false, and how to prove it.

Thanks. :smile:
I am not sure but the result depends on the value of s and t since they are not unique in a given problem
 
  • #3


The result is true. To prove it, we can use the definition of greatest common factor (GCF).

Let d = gcd(z,nm). This means that d is a common divisor of both z and nm.

We know that z = smi + tnj (mod nm), so z is congruent to 1 (mod nm). This means that z and nm have a common factor of 1.

Since gcd(n,m) = 1, we know that d_n and d_m are the only divisors of n and m, respectively. This means that d_n and d_m are the only common divisors of n and m.

Since d_n is a divisor of n, we know that d_n is also a divisor of nm. Similarly, d_m is a divisor of nm.

Since d is a common divisor of z and nm, we know that d is also a divisor of d_n and d_m. This means that d is a common divisor of d_n and d_m.

Therefore, d is a common divisor of d_n and d_m, and it must be the greatest common factor of d_n and d_m.

Hence, we can conclude that gcd(z,nm) = d_nd_m, proving the given statement.
 

What is a greatest common factor?

A greatest common factor, also known as a greatest common divisor, is the largest number that can evenly divide into all given numbers.

How do you find the greatest common factor?

To find the greatest common factor, you can list all the factors of each number and then identify the largest number that appears in all lists. Another method is to use the prime factorization of each number and then identify the common prime factors.

Why is finding the greatest common factor important?

Finding the greatest common factor is important because it can help simplify fractions, factor polynomials, and solve problems involving ratios and proportions.

Can the greatest common factor be larger than one of the given numbers?

No, the greatest common factor cannot be larger than any of the given numbers. The greatest common factor is always a factor of both given numbers, so it must be smaller or equal to both of them.

What is the difference between greatest common factor and least common multiple?

The greatest common factor is the largest number that can divide into both given numbers, while the least common multiple is the smallest number that is a multiple of both given numbers. In other words, the greatest common factor is a divisor, while the least common multiple is a multiple.

Similar threads

  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
4
Views
899
  • Calculus and Beyond Homework Help
Replies
2
Views
902
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
977
Replies
5
Views
2K
Replies
6
Views
909
  • Engineering and Comp Sci Homework Help
Replies
1
Views
962
Replies
19
Views
4K
  • Linear and Abstract Algebra
Replies
2
Views
2K
Back
Top