2
$\begingroup$

Is $(2^2-1)(3^2-1)(4^2-1)....(300^2-1)$ divisible by $7^{95}$?

And what about $7^{100}$?

This is taken out of one of the TAU entry tests.

I seem to always have a struggle with these exercises, probably because I don't enough experience.

What I've tried is to see if I can notice some pattern in the sequence but that really didn't add much except that I know for sure that it's divisible by 7.

Another thing that I tried is to set the sequence like this: $((7-5)^2-1)((7-4)^2-1)((7-3)^2-1)...((7+293)^2-1)$

But unfortunately, I can't really see how that helps me either, I still can't extract a 7 out of the expression.

$\endgroup$
  • 5
    $\begingroup$ It might help to rewrite all the $(a^2-1)$ as $(a+1)(a-1)$ and then counting how many of them are multiples of $7$ $\endgroup$ – Osama Ghani Jul 19 '18 at 13:01
  • $\begingroup$ It helps that none of these terms are divisible by $7^3$ (as $7^3>300$). So you just have to count the multiples of $7$ and then add $1$ for each multiple of $7^2$. $\endgroup$ – lulu Jul 19 '18 at 13:05
3
$\begingroup$

Note that $x^2-1=(x-1)(x+1)$. Then $$ (2^2-1)(3^2-1)\cdots (300^2-1)=(2-1)(2+1)(3-1)(3+1)\cdots(300-1)(300+1). $$ Since $49=7^2 < 300 < 7^3=343$, we will check the number of multiples of $7$ and $49$. Since $7\cdot 43=301$ and $7\cdot 44=308$, the number of multiples of $7$ less than $300$ and $302$ is $42$ and $43$, respectively. Also, since $49\cdot 6=294$ and $49\cdot 7=343$, the number of multiples of $49$ less than $300$ and $302$ is $6$ and $6$, respectively. $42+43+6+6=97$ and $n=97$ is the maximum such that $7^n$ divides $(2^2-1)(3^2-1)\cdots (300^2-1)$. Therefore $(2^2-1)(3^2-1)\cdots (300^2-1)$ is divisible by $7^{95}$ but not divisible by $7^{100}$.

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