Solve modular arithmetic equation $\frac{1}{24} \cdot n(n+1)(n+2)(n+3) \equiv 1 \pmod{10}$

Question

From another problem, I have reduced it to: This is the last step in solving:

Solve $\frac{1}{24} \cdot n(n+1)(n+2)(n+3) \equiv 1 \pmod{10}$

How should I begin, a major problem is the $1/24$

I think there is something wrong with your equation. 24 is not invertible in $\mathbb Z/10\mathbb Z$ ! — ayberk, Nov 16 '15 at 14:35
Isn't n=1 a trivial soluution ? The product of any 4 consecutive numbers is always divisible by 24 — Shailesh, Nov 16 '15 at 14:41
consider $4!$ so product of all numbers starting from 1 will be divisible by $24$. — Archis Welankar, Nov 16 '15 at 14:42

score 2 · Accepted Answer · answered Nov 16 '15 at 15:46

2

You want to find $n$ such that $$n(n+1)(n+2)(n+3)\equiv 24\pmod{240}\tag1$$

By the way, $$\begin{align}(1)&\Rightarrow n(n+1)(n+2)(n+3)\equiv 4\pmod{10}\\\\&\Rightarrow n\equiv 1,6\pmod{10}\end{align}$$

So, you only need to check if each of the following 48 numbers satisfies $(1)$ : $$1,11,21,\cdots, 231$$ $$6,16,26,\cdots, 236$$

Hence, the answer is $$\small n\equiv 1,11,26,36,41,51,66,76,81,91,106,116,121,131,146,156,161,171,186,196,201,211,226,236\pmod{240}$$

answered Nov 16 '15 at 15:46

mathlove

139,939

How did you get the $24 \pmod{240}$ part (+1) as always – Amad27 Nov 16 '15 at 16:01
@Amad27: We have $\frac{1}{24}n(n+1)(n+2)(n+3)=1+10k$ for some $k\in\mathbb Z$ $\iff$ $n(n+1)(n+2)(n+3)=24+240k$. – mathlove Nov 16 '15 at 16:05
So $n \equiv 1,11,26,$ or $36$ mod $40$. Or: $n \equiv 1$ mod $5$, and $n \equiv 1,2,3,$ or $4$ mod $8$. – TonyK Nov 16 '15 at 16:19
@TonyK: Thanks, I didn't notice that. – mathlove Nov 16 '15 at 16:23
Damn mathlove. Just damn. Then how did the reduction go to the next step? The part with $4 \pmod{10}$ – Amad27 Nov 16 '15 at 16:24
@Amad27: See the equation $n(n+1)(n+2)(n+3)=24+240k$ in mod 10. Since $24\equiv 4\pmod{10}$, we have $n(n+1)(n+2)(n+3)\equiv 4\pmod{10}$. – mathlove Nov 16 '15 at 16:26
So then, $n = 10k + 4$ for example right? This is from: http://math.stackexchange.com/questions/1530635/how-many-numbers-have-unit-digit-1/1530726?noredirect=1#comment3119663_1530726 so then we set $n <= 2014$ get that $k < 201$, But Thomas Andrews pointed out something about $n=6$? – Amad27 Nov 16 '15 at 16:49
@Amad27: Note that $n(n+1)(n+2)(n+3)\equiv 4\pmod{10}$ is a necessary condition. (I used $\Rightarrow$, and I didn't use $\iff$) This is not a sufficient condition. I used the necessary condition to restrict the possibilities for $n$. So, at the end, we need to check the sufficiency as I did in my answer. – mathlove Nov 16 '15 at 16:52
@Amad27: Maybe I misunderstood your question. We don't have $n=10k+4$. We have $n=10k+1$ or $n=10k+6$ from $n(n+1)(n+2)(n+3)\equiv 4\pmod{10}$. (why?) – mathlove Nov 16 '15 at 17:06
Mmm... I dont see why? Explain please? – Amad27 Nov 16 '15 at 17:26
@Amad27: For $n\equiv 0\pmod{10}$, $n(n+1)(n+2)(n+3)\equiv 0\cdot 1\cdot 2\cdot 3\equiv 0\not\equiv 4\pmod{10}$, so we have $n\not\equiv 0\pmod{10}$. For $n\equiv 1\pmod{10}$, $n(n+1)(n+2)(n+3)\equiv 1\cdot 2\cdot 3\cdot 4\equiv 24\equiv 4\pmod{10}$, so we have $n\equiv 1\pmod{10}$. For $n\equiv 3\pmod{10}$, ... Can you continue from here to $n\equiv 9\pmod{10}$? – mathlove Nov 16 '15 at 17:29
I see, $n\equiv 1$ and $n \equiv 6$ are the ones that work. That gives$n = 1 + 10k, n = 6 + 10k$. But then a problem this causes is that, there are: $200 + 201 = 401$ values of $n$? The answer however, is $202$ values? – Amad27 Nov 17 '15 at 12:34
@Amad27: Sorry, but I don't get what you mean. We have $1,11,21,\cdots, 231$ and $6,16,26,\cdots, 236$. So, $24+24=48$ values of $n$ because we want $n$ such that $1\le n\le 240-1$. – mathlove Nov 17 '15 at 12:38
@mathlove, my bad. I meant from here: http://math.stackexchange.com/questions/1530635/how-many-numbers-have-unit-digit-1/1530726?noredirect=1#comment3119663_1530726 The range of $n$ is $1 \to 2014$, so that will give an incorrect answer? – Amad27 Nov 17 '15 at 12:49
@Amad27: Then, just count the number of $n$ such that $n\equiv 1,11,26,36\pmod{40}$ and $1\le n\le 2014$. (TonyK pointed out that the former is equivalent to my answer.) – mathlove Nov 17 '15 at 12:52
@Amad27: Note that $n=1+10k,6+10k$ is a necessary condition. This is not sufficient. (Please read my answer carefully) By the way I got $202$ values of $n$. – mathlove Nov 17 '15 at 13:07
Wait okay. Let me rethink. Why do the numbers need to satisfy $(1)$? – Amad27 Nov 17 '15 at 13:22
@Amad27: I answered the question because the question is the same as your first comment, right? see my first comment. Note that $(1)$ is the necessary and sufficient condition. – mathlove Nov 17 '15 at 13:24

score 1 · Answer 2 · answered Nov 16 '15 at 19:45

$$\tfrac1{24}n(n+1)(n+2)(n+3)\equiv 1\mod 10\iff n(n+1)(n+2)(n+3)\equiv 24 \mod 240$$ Using the Chinese remainder theorem, this is equivalent to solving the system of congruences: $$p(n)=n(n+1)(n+2)(n+3)\equiv\begin{cases}0\mod3 \\ 4\mod5\\8\mod 16 \end{cases}$$ The only solution to the second congruence is $\;n\equiv 1\mod 5$, whence the solutions to the first two: $$\color{red}{n_1\equiv 1,6,7\mod15}. $$

We'll determine the values of the factors and of $p(n)$, according to the value of $n\bmod 16$: $$\begin{array}{r|cccc||r|cccc} n\equiv&n+1&n+2&n+3&p(n)&n\equiv&n+1&n+2&n+3&p(n) \\ \hline 0&1&2&3&0&8&9&10&11&0\\ 1&2&3&4&8&9&10&11&12&8\\ 2&3&4&5&8&10&11&12&13&8\\ 3&4&5&6&8&11&12&13&14&8\\ 4&5&6&7&8&12&13&14&15&8\\ 5&6&7&8&0&13&14&15&0&0\\ 6&7&8&9&0&14&15&0&1&0\\ 7&8&9&10&0&15&0&1&2&0 \end{array}$$ Thus the solutions of the second congruence are $\;\color{red}{n_2\equiv 1,2,3,4,9,10,11,12\mod16}$.

Byy the inverse isomorphism of the Chinese remainder theorem, from the Bézout's relation: $\;16-15=1$, we obtain the $24$ solutions: $$\color{red}{n\equiv 16n_1-15n_2\mod 240}.$$

score 0 · Answer 3 · answered Nov 16 '15 at 20:17

Okay enough of this mod $240$ nonsense, the prime $3$ is irrelevant and you have an extra power of $2$ for some reason. As someone in the comments said, this equation is just ${n+3 \choose 4} \equiv 1 \mod 10$.

Now a nice fact to know is that as a function of $n$ the binomial coefficients $n \choose k$ are periodic modulo any prime $p$ with period $p^ {\lceil log_p(k+1)\rceil}$. If you want to know why this is true, look up Lucas' theorem on binomial coeffients.

So for $k=4$ this means the function ${n+3 \choose 4}$ is periodic modulo $2$ with period $8$, and periodic mod $5$ with period $5$. Solving these separately we see $n \equiv 1,2,3,4 \mod 8$ and $n \equiv 1 \mod 5$ giving solutions $n \equiv 1,11,26,36 \mod 40$. This gives the same answers as mathlove just less redundant.

Solve modular arithmetic equation $\frac{1}{24} \cdot n(n+1)(n+2)(n+3) \equiv 1 \pmod{10}$

3 Answers3