1
$\begingroup$

I am preparing for the CAT and am not allowed to use a calculator to solve questions like these

If k is an integer and $\frac{35^2-1}{k}$ is also an integer then k could be any of the following except a)8 b)9 c)12 d)16 e)17 (Ans=D)

Are there any properties that I might use here to get the answer without using a calculator

$\endgroup$
  • 3
    $\begingroup$ You could note $35^2-1=(35+1)(35-1)$ and test the possibilities. $\endgroup$ – David Mitra Jul 20 '12 at 3:03
  • $\begingroup$ @DavidMitra Thanks thats a good one. However if the power was 5 instead ? $\endgroup$ – MistyD Jul 20 '12 at 3:03
  • 1
    $\begingroup$ Modular arithmetic: replace $35$ by its remainder, square, replace the result by its remainder, subtract $1$. If you don't get $0$, it's not divisible by that. For example, $35$ has remainder $8$ (or $-1$) modulo $9$. So $35^5$ has remainder $(-1)^5 = -1$ modulo $9$. So $35^5-1$ has remainder $-2=7$ modulo $9$, hence is not a multiple of $9$. $\endgroup$ – Arturo Magidin Jul 20 '12 at 3:05
1
$\begingroup$

It cannot be $16$.

The reason is that if you divide $35$ by any of $9$, $12$, or $17$, the remainder is $\pm 1$. That means that when you divide $35^2$ by any of $9$, $12$, or $17$, the remainder is $(\pm 1)^2 = 1$. So if you then subtract $1$, you get an exact multiple.

Similarly, if you divide $35$ by $8$, the remainer is $3$; so when you divide $35^2$ by $8$, the remainder is the same as the remainder of $3^2=9$, which is $1$; again, you get a multiple when you subtract $1$.

But when you divide $35$ by $16$ the remainder is $3$; squaring, the remainder is $9$. Subtract $1$, the remainder is $8\neq 0$.

$\endgroup$
  • 1
    $\begingroup$ Thanks this will come in handy $\endgroup$ – MistyD Jul 20 '12 at 3:09
0
$\begingroup$

Note that the equation can be factored into the form: $$\frac{\left(35+1\right)\left(35-1\right)}{k}$$ using difference of squares. Since $\left(35^2 -1\right)|k$, it follows either $\left(35 + 1\right)|k$ or $\left(35 -1\right)|k$. Since $16$ is the only number not a factor of $\left(35 -1\right)$ nor $\left(35 +1\right)$ it follows $k$ cannot be $16$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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