Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer

Your Answer

 
discard

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.