# Math Help - Find the divisor...

1. ## Find the divisor...

I havn't found an easy way yet, appreciate any help/working/thoughts.
Narrowed it down to be less than 100 and greater than 30 (I think...pretty sure) by sheer number crunching.
Here's the problem...

When 823519 is divided by a number which is bigger than 1, ther remainder is three times the remainder obtained by dividing 274658 by the same number. Find the divisor.

2. By the division algorithm ( $a=bq+r$ with $q=\lfloor \frac{a}{b} \rfloor$ (Here $\lfloor x \rfloor$ denotes the largest integer not greater than x)) we have

$274658=m\left(\lfloor\frac{274658}{m}\rfloor \right)+r$

So
$r = 274658-m \left(\lfloor\frac{274658}{m}\rfloor \right)$

$823519 \equiv 3 \left(274658-m \lfloor\frac{274658}{m}\rfloor \right)\mod m$
$\Rightarrow m|823974-3m\left(\lfloor \frac{274658}{m} \rfloor\right) - 823519$
$\Rightarrow m|455 \times 1 - 3m\left(\lfloor \frac{274658}{m} \rfloor \right)$

And because of the divisibility property: If $a|b$ and $a|c$ then $(\forall m,n \in \Re) \ a|bm+cn$

So m divides one of $455$ or $1$. But since another property states that if $a|b \Rightarrow b \geq a$, and since it is a requirement that $m \neq 1$, we must have $m|455$

Then m is a factor of 455

The factors of 455 are: 1, 455, 5, 91, 7, 65, 13, 35

By trial I get m = 91