Is the Formula for GCD(z, nm) = d_n*d_m Correct?

[xuying1209]

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.

 

[malaygoel]

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.

I am not sure but the result depends on the value of s and t since they are not unique in a given problem

 

[tacman]

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.