I started a Computer Science degree this year and I have a subject called 'Discrete Mathematics' which this unit (divisibility) is annoying me a lot, because I can't find the key to solve the problems as like as other units and subjects.
The problem that I can't solve is this:
Find two integer numbers 'a' and 'b' given that their difference is 1080 and their LCM is 3900
Thanks
On
Here is a brute force approach (involving only six cases to check total, so relatively short for brute force)
We first recognize that if $\text{lcm}(a,b)=3900$ then $3900$ is a multiple of both $a$ and $b$ implying that both $a$ and $b$ are factors of $3900$.
The factorization is $3900=2^2\cdot 3\cdot 5^2\cdot 13$
The $36$ factors of $3900$ are $\left\{\begin{array}{}1&2&3&4&5&6&\dots\\\dots&260&300&325&390&650\\780&975&1300&1950&3900\end{array}\right\}$
Assume without loss of generality that $a>b$. If we are looking for positive integers $a$ and $b$, then since $a-b=1080$ it must be that $a=b+1080\geq 1080$ and there are only three candidates for the value of $a$ which are larger than $1080$.
Unfortunately, $3900-1080=2820$ is not a factor of $3900$, $1950-1080=870$ is not a factor of $3900$, and $1300-1080=220$ is not a factor of $3900$, so there are no positive values of $a$ and $b$ that work.
If we allow for negative values of $a$ and $b$, then we can extend our search further. Without loss of generality, let $|a|>|b|$ for the remainder of our search.
With $|a|>|b|$ and $a-b=1080$, since $|a-b|=1080\leq |a|+|b|<2|a|$ we have that $|a|>540$ so this adds only three additional cases to check by hand.
Continuing the search, we get $975-1080=-105$ is not a factor of $3900$, and $650-1080=-430$ is not a factor of $3900$, however $780-1080=-300$ is in fact a factor of $3900$
Indeed, checking $\text{lcm}(780,-300)=3900$ as $780=2^2\cdot 3\cdot 5\cdot 13$ and $300=2^2\cdot 3\cdot 5^2$
On
$3900=2^2\cdot3^1\cdot5^2\cdot13^1$
$1080=2^3\cdot3^3\cdot5^1$
Since the difference of $1080$ is divisible by $2^2$, this component must be in both numbers.
Since the difference of $1080$ is divisible by $3^1$, this component must be in both numbers.
Since the difference of $1080$ is divisible by $5^1$, this component must be in both numbers.
Since the difference of $1080$ is not divisible by $5^2$, this component cannot be in both numbers.
Since the difference of $1080$ is not divisible by $13^1$, this component cannot be in both numbers.
This leaves us with only the following options:
In the second option, we have $a+b=300+780=1080$.
So take exactly one of them as negative, and you have the answer.
On
HINT:
Let $(a,b)=d$ and $\dfrac aA=\dfrac bB=d\implies(A,B)=1$
$d(A-B)=1080$
and lcm$(a,b)=ABd=3900$
$\implies\dfrac{3900}{1080}=\dfrac{ABd}{d(A-B)}$
$\implies B=\dfrac{65A}{18A+65}$
Now if integer $D$ divides both $65A,18A+65;$
as $B$ is an integer, $D$ must divide $65(18A+65)-18(65A)=65^2$
and $18A+65$ must divide $65^2$
In the search of a more elegant solution rather than brute force, we know that as $\text{lcm}(a,b)=2^2\cdot 3\cdot 5^2\cdot 13$ that if both $a$ and $b$ had a factor of $13$ that $a-b$ must also be divisible by $13$. Similarly if both $a$ and $b$ had a factor of $5^2$ that $a-b$ must be divisible by $5^2$.
Since $a-b=1080$ is not divisible by $13$ nor divisible by $25$, we know that exactly one of the two is divisible by $13$ and that exactly one of the two is divisible by $25$.
Also, since $a-b=1080=2^3\cdot 3^3\cdot 5$, one can also reason that both $a$ and $b$ must be divisible by $2^2\cdot 3\cdot 5=120$.
(They must both be divisible by four because otherwise one will be divisible by four and the other is not, implying their difference would not have been divisible by four which is a contradiction. similarly for the other factors. In general, try proving that $\gcd(a-b,\text{lcm}(a,b))$ divides both $a$ and $b$)
This brings our candidate answers to either $|a|=2^2\cdot 3\cdot 5^2\cdot 13=3900$ and $|b|=2^2\cdot 3\cdot 5=120$ or $|a|=2^2\cdot 3\cdot 5\cdot 13=780$ and $|b|=2^2\cdot 3\cdot 5^2=300$
It is clear that since $|3900\pm 120|>3780> 1080$ that it could not be the first result.
The second result on the other hand does work with $780-(-300)=1080$, yielding $a=780$ and $b=-300$. We already know that $\text{lcm}(780,-300)=3900$ by construction.