Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have three variables $x,y,z$, but I want to find the smallest positive $M$ for which $M*M*x*y$ is divisible by $2*z*M$ which is the same as modulo 0. Can I do this without needing to brute check all values of $M$?

share|cite|improve this question
By $\ast$, do you mean multiplication? – Peter LeFanu Lumsdaine Dec 3 '12 at 18:56
@PeterLeFanuLumsdaine Yes – KaliMa Dec 3 '12 at 18:57
up vote 1 down vote accepted

$2Mz$ divides $M^2xy$ if and only if $2z$ divides $Mxy$. So the question is just: find the least positive $M$ such that $Mxy$ is divisible by $2z$.

But this can be rephrased as: find the least positive multiple of $xy$ that is also a multiple of $2z$. So we want $Mxy = \mathop{\mathrm{lcm}} (xy, 2z)$; so the solution is: $$M = \frac{\mathop{\mathrm{lcm}}(xy,2z)}{xy}.$$

share|cite|improve this answer

Hint $\rm\,\ 2zM\mid xyM^2\!\iff\! 2z\mid xy M\!\iff\! 2z\mid (xy,2z)M\!\iff\! \color{#C00}{2z/(xy,2z)}\mid M,\ \ \, $ (a,b) = gcd(a,b)

Or: $ $ said dually $\rm\!\iff\! xy,2z\mid xyM\!\iff\!\, [xy,2z]\mid xyM\!\iff\!\, \color{#0A0}{[xy,2z]/xy}\mid M,\ \ \ [a,b] = lcm(a,b)$

They're equivalent by the $\rm\,gcd * lcm\:$ formula $\rm\ ab = (a,b)[a,b] = gcd(a,b)\,lcm(a,b),\ $ so

$$\rm (xy,2z)[xy,2z]\, =\, xy\,2z\ \ \Rightarrow\ \color{#C00}{\dfrac{2z}{(xy,2z)}}\, =\, \color{#0A0}{\dfrac{[xy,2z]}{xy}}$$

Remark $\ $ You can find many more examples of such universal proofs of gcd and lcm properties in my prior posts. Learning these techniques makes the proofs mechanical, just like calculus makes calculating volumes mechanical.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.