Modular Arithmetic: Exploring the Relationship Between a, b, and m

[imagination10]

ab ≡ 0 (mod m), where a and b are positive integer < m.
Does it follow that either a| m or b| m?


Can anyone give a proof for this ?

 

[mathman]

Not true. Example: a=8, b=9, m=12.

 

[tacman]

Yes, it does follow that either a| m or b| m. This can be proven using the Fundamental Theorem of Arithmetic, which states that every positive integer can be expressed as a unique product of prime numbers.

Since a and b are both positive integers less than m, they can be expressed as the product of prime numbers as well. Let's say that a = p1^x1 * p2^x2 * ... * pn^xn and b = q1^y1 * q2^y2 * ... * qn^yn, where p and q are prime numbers and x and y are positive integers.

Now, if ab ≡ 0 (mod m), then this means that ab is divisible by m. This can also be written as ab = km, where k is some positive integer.

Substituting the prime factorizations of a and b, we get:

(p1^x1 * p2^x2 * ... * pn^xn) * (q1^y1 * q2^y2 * ... * qn^yn) = km

Expanding this, we get:

p1^x1 * p2^x2 * ... * pn^xn * q1^y1 * q2^y2 * ... * qn^yn = km

Since a and b are both less than m, all of their prime factors must also be less than m. This means that all of the prime factors on the left side of the equation must also be less than m.

Therefore, in order for km to be divisible by m, at least one of the prime factors on the left side must be equal to m. This can only happen if either a or b contains m as one of its prime factors.

Hence, either a| m or b| m. This completes the proof.