# $n$ such that $9$ divides $(n+3)(n-3)(n+1)(n-1)(n-100)$

How should one systematically proceed to find $n \in \mathbb{Z}$ such that $9$ divides $(n+3)(n-3)(n+1)(n-1)(n-100)$? Equivalently, how does one solve the following congruence? $$(n+3)(n-3)(n+1)(n-1)(n-100) \equiv 0 \mod 9$$

If $9$ were a prime number, then this would be easy enough, but since $9$ is not prime, how does one solve the problem in the most straightforward way?

Analogously, how should one approach $$(n+3)(n-3)(n+1)(n-1)(n-100) \equiv 0 \mod 4,$$ which, although similar to the first problem, seems more tricky?

• In which exact way do you think it as easier in case you have a prime modulus. Differently, what would you want to do that you cannot do with a general modulus. – quid Feb 11 '16 at 20:39
• @quid If $p$ is prime and divides $a_1 \cdots a_n$, then $p|a_1$ or ... or $p|a_n$, which is not true in general. – user310769 Feb 11 '16 at 20:48
• That''s a good point. I did not think of it that way. – quid Feb 11 '16 at 20:50

$$f(n)=(n^2-9)(n^2-1)(n-100)\equiv n^2(n-1)^2(n+1)\pmod9$$

Now $3$ can divide exactly one of $n,n-1,n+1$

Clearly, if $n\equiv0,1\pmod3,9|f(n)$

Else $n\equiv-1\pmod3$ and $9\mid f(9)\iff9\mid(n+1)\iff n\equiv-1\pmod9\equiv8$

$n=0$ modulo $3$ will work thanks to $n+3$ and $n-3$.

$n=1$ modulo $3$ will work thanks to $n-1$ and $n-100$.

$n=8$ modulo $9$ will work thanks to $n+1$.

So the answer is $n=0,1,3,4,6,7,8$ modulo $9$.

The critical idea is that $3$ is the only prime divisor of $9$ and exactly one of $(n+3,n-3)$, $(n-1,n-100)$ and $n+1$ is divisible by $3$.

$(n+3)(n-3)(n+1)(n-1)(n-100) \equiv 0 \mod 4$

$(n -1)(n + 1)(n + 1)(n -1)n \equiv 0 \mod 4$ (as $3,-3,100 \equiv -1, 1, 0 \mod 4$).

If $n \equiv 0 \mod 2$ then $n$ is a solution (as $n|(n -1)(n + 1)(n + 1)(n -1)n$ and $n \equiv 0 \mod 4$) .

If $n \equiv 1 \mod 2$ then $n$ is a solution (as $(n-1)|(n -1)(n + 1)(n + 1)(n -1)n$ and $n -1 \equiv 0 \mod 4$)

The only numbers that are not solutions are $n \equiv 2 \mod 4$ as

$(n -1)(n + 1)(n + 1)(n -1)n \equiv 1^2(-1)^2 \equiv 2 \mod 4$

• You have some mistakes. You probably meant "If $n\equiv 0\pmod{4}$". In the second case, you said "if $n\equiv 1\pmod{2}$" but then "and $n-1\equiv 0\pmod{4}$". Etc. – user236182 Feb 12 '16 at 1:57