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

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.

• 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$ – Osama Ghani Jul 19 '18 at 13:01
• 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$. – lulu Jul 19 '18 at 13:05

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