# Solving a fraction expression without a calculator using properties

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

-
You could note $35^2-1=(35+1)(35-1)$ and test the possibilities. – David Mitra Jul 20 '12 at 3:03
@DavidMitra Thanks thats a good one. However if the power was 5 instead ? – MistyD Jul 20 '12 at 3:03
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$. – Arturo Magidin Jul 20 '12 at 3:05

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$.

-
Thanks this will come in handy – MistyD Jul 20 '12 at 3:09

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$.

-