# n(n+1) as a multiple of 100

Here's a puzzle I came up with while walking today:

For how many natural numbers $$n$$ is the number $$n(n+1)$$ a multiple of $$100$$?

• This is true for infinitely many $$n$$, so "how many" means something like "one in every hundred $$n$$", an answer in that sort of form.
• There are some brute-forcey ways to do this, but also some nice shortcuts. Checkmark will go (eventually) to the neatest solution.

First,

We have $$(n,n+1)=1$$. So either $$4\mid n$$ or $$4\mid n+1$$, and either $$25\mid n$$ or $$25\mid n+1$$.

So,

We have the $$n\equiv-1,0\pmod4$$ and $$n\equiv-1,0\pmod{25}$$. After solving, we have $$n\equiv0,24,75,99\pmod{100}$$ are all the integers that fit the requirement.

Edit(More elegant):

Wait a minute, the author only required us to find the number of solutions! So by CRT, as there are two remainders which we need when $$n$$ is divided by $$4$$ and $$25$$, we have $$2\times2=4$$ solutions per $$25\times4=100$$ consecutive integers.

• This is correct (+1), but there's a trick to shortcut around part of this, making it not just a standard application of the Chinese Remainder Theorem :-) – Rand al'Thor May 28 at 8:54
• @Randal'Thor Edited! – Culver Kwan May 28 at 10:13
• @Randal'Thor Is this your method? – Culver Kwan May 31 at 2:23
• Sorry for not responding to your edit. I left a comment on Jaap's answer; his second method is what I had in mind. But when I come to accept an answer on this, I'll have a think about whether to accept that one or if anyone else's is simpler / more elegant. – Rand al'Thor May 31 at 6:35
• @Randal'Thor, No, isn’t my method more elegant? I used the property of uniqueness of solution, and found the number of solutions. – Culver Kwan May 31 at 10:58

Consider two consecutive numbers $$n$$ and $$n+1$$.

Suppose the first is a multiple of $$a$$, the second a multiple of $$b$$.
Since consecutive numbers are coprime, $$a$$ and $$b$$ are coprime.
We want to count all those cases where $$a*b=100$$, which are therefore the four cases $$(a,b) \in \{ (1,100), (100,1), (4,25), (25,4) \}$$. In each case we have a pair of modular equations $$n\equiv 0 \mod a \\ n+1\equiv 0 \mod b$$ The Chinese Remainder Theorem gives a unique solution modulo $$a*b=100$$, so there are exactly $$4$$ solutions in every block of $$100$$ consecutive numbers, or $$1$$ in $$25$$.

Edit: Here's a different, possibly simpler argument:

Clearly one of the two consecutive numbers needs to be a multiple of $$25$$. Pick any multiple of $$25$$.
If this is an odd number, then its neighbours are both even and differ by two, so exactly one of its neighbouring numbers is a multiple of $$4$$, and we get one solution to the problem.
If it is even and a multiple of $$4$$, then it is itself a multiple of $$100$$ and we can combine it with either of its neighbours, so this gives two solutions to the problem.
If it is even but not a multiple of $$4$$, then it cannot form a solution with either of its neighbours since they are both odd.
On average we get one solution for every multiple of $$25$$.

• Nice, you've managed to count them without explicitly solving the Chinese Remainder Theorem congruences. But there's a trick to shortcut around using CRT. – Rand al'Thor May 28 at 8:58
• Yep, your second argument is pretty much what I was thinking of. Surprisingly enough, CRT isn't (explicitly) needed at all to solve this problem. – Rand al'Thor May 28 at 13:29

In the "degenerate" case:

Any solution where n=m*100 or n+1=m*100 works. This occurs twice for every hundred.

In any other case, specific conditions must be met:

100 factors as two 2s and two 5s, so those factors must be contained in n and n+1.

However, we can easily narrow it further:

If n has 2 or 5 as a factor, n+1 does not. Therefore one term must have two 5s and the other must have 2 twos. The only adjacent integers satisfying this are 24,25 and 75,76, so n=24 or n=75. This works for every m*100+n, since m*100 contains two 2s and two 5s.

Combining the two cases:

4% of integers satisfy the condition.

Using the well-known summation formula, $$\sum_{i=1}^n i = \frac{(n+1)n}{2}$$, the question is equivalent to how often $$\sum_{i=1}^n i$$ is a multiple of $$50$$. To get a multiple of $$100$$, $$n$$ and $$n+1$$ together must contain two factors of $$5$$. Since $$n$$ and $$n+1$$ cannot both be a multiple of $$5$$, at least one of them is a multiple of $$25$$.

Now observe that

if we enumerate the cases of $$n=a\cdot 25$$ and $$n=a\cdot 25 - 1$$ for some positive integer $$a$$ with $$n\leq 50$$, we get \begin{align}\sum_{i=1}^{24} i &= (24\cdot 25)/2 = 3\cdot 4\cdot 25 \equiv 0 \mod 50\\ \sum_{i=1}^{25} i &\equiv 25 \mod 50 & \text{(follows from line above)}\\ \sum_{i=1}^{49}i &= (49\cdot 50)/2 = 49 \cdot 25\equiv 25 \mod 50 \\ \sum_{i=1}^{50} i &\equiv 25 \mod 50 & \text{(follows from line above)}\end{align} Since we work modulo $$50$$, the values for $$n\in [51,100]$$ will be those of $$[0,50]$$ plus $$25$$. This means $$75, 99, 100$$ are exactly the values when the summation is $$0\mod 50$$. So, $$24,75,99,100$$ are all the solutions in $$[1,100]$$, and since $$\sum_{i=1}^{100} i = 0\mod 50$$, these solutions are periodic with a period of length $$100$$. Therefore, for every $$4$$ out of $$100$$ integers $$n$$, $$n(n+1)$$ is a multiple of $$100$$

(To reflect a puzzle that came up while walking, here’s a general solution that also came up while walking. This write-up was reorganized a few days after posting.)

$$\begingroup \def \b #1{ \boldsymbol{#1} } \def \F #1#2{ {\LARGE\strut} \f{#1}{#2} } \def \f #1#2{ { \large #1 \over \large #2 } } \def \Q #1#2{ { \large\frac{2^{\Large\kern.05em\b{#1}}}{#2} } } \def \t #1{ {\small\textsf{#1}} } \def \x { { \scriptsize\raise.2ex\times}\kern.1em } \def \& #1{ & \kern-.9em #1 \kern-1em & } \def \+ { { \kern.1em + } } \def \/ { \\[-.4ex] }$$The probability that $$n(n\+1)$$ is a multiple of $$100$$ is ...

$${ 2^{\large (\textsf{how many distinct prime factors of}~100)} \over 100 } ~=~ { 2^{\large 2} \over 100} ~=~ { 1 \over 25}$$

This works in general for $$n(n\+1)$$ that might be a multiple of any $$m \ge 2$$. (In the puzzle, $$m=100$$.)

$$\begin{matrix} \begin{matrix} \\ m \\ \t{(as an example)} \end{matrix} && \begin{matrix} \\ \t{Prime} \/ \t{factorization} \/ \t{of}~ m \end{matrix} && \begin{matrix} \strut D(m) ~ = \/ \t{how many} \/ \t{distinct prime} \/ \t{factors of}~ m \end{matrix} && \begin{matrix} {\Large{2^{D(m)} \over \raise.3ex m}} ~ = \/ \t{probability that} \/ n(n\+1) ~\t{is a} \/ \t{multiple of}~ m \end{matrix} \\[1ex]\hline 2 && 2^1 && 1 && \Q{1}{2} ~=~ 1 \\ 3 && 3^1 && 1 && \Q{1}{3} ~=~ \F{2}{3} \\ 4 && 2^2 && 1 && \Q{1}{4} ~=~ \F{1}{2} \\ 6 && 2^1 \x 3^1 && 2 && \Q{2}{6} ~=~ \F{2}{3} \\ 72 && 2^3 \x 3^2 && 2 && \Q{2}{72} ~=~ \F{1}{18 } \\ \boldsymbol{100}&&\b2^2 \x \b5^2 &&\b2 && \t{(already mentioned)} \\ 4725 && 3^3 \x 5^2 \x 7^1 && 3 && \Q{3}{4725} ~=~ \F{8}{4725} \end{matrix}$$

Sure enough, the probabilities are the same for $$m = 3$$ and $$m = 6 = 3 \x 2$$. After all, $$n(n\+1)$$ is always divisible by $$2$$.

And, sure enough, $$2^{\large (\textsf{how many distinct prime factors of}~4725)} {=}~ 8$$ instances of $$n(n\+1)$$ among the $$4725$$ values of $$1 \le n \le 4725$$ are divisible by $$m = 4725 = 3^3 \x 5^2 \x 7^1$$.

$$\small\begin{array}{rrlcrrlrrrlcrrl} 350 \&\x 351 &=& ( 5^2 \x 7 ) \&\x 2 ~\&\x~ 13 \&\x ( 3^3 ) &=& 26 \&\x 4725 \\ 1350 \&\x 1351 &=& ( 3^3 \x 5^2 ) \&\x 2 ~\&\x~ 193 \&\x ( 7 ) &=& 386 \&\x 4725 \\ 1700 \&\x 1701 &=& ( 5^2 ) \&\x 68 ~\&\x~ 9 \&\x ( 3^3 \x 7 ) &=& 612 \&\x 4725 \\ 3024 \&\x 3025 &=& ( 3^3 \x 7 ) \&\x 16 ~\&\x~ 121 \&\x ( 5^2 ) &=& 1936 \&\x 4725 \\ 3374 \&\x 3375 &=& ( 7 ) \&\x 482 ~\&\x~ 5 \&\x ( 3^3 \x 5^2 ) &=& 2410 \&\x 4725 \\ 4374 \&\x 4375 &=& ( 3^3 ) \&\x 162 ~\&\x~ 25 \&\x ( 5^2 \x 7 ) &=& 4050 \&\x 4725 \\ 4724 \&\x 4725 &=& \&{} 4724 ~\&\x~ 1 \&\x ( 3^3 \x 5^2 \x 7 ) &=& 4724 \&\x 4725 \\ 4725 \&\x 4726 &=& ( 3^3 \x 5^2 \x 7 ) \&\x 1 ~\&\x~ 4726 \&{} &=& 4726 \&\x 4725 \end{array}$$

Why this works, with $$m = 4725$$ as an example:

1. The combined prime factors of $$n$$ and $$n\+1$$ must include the prime factors of $$4725$$, namely at least three $$3$$s, two $$5$$s and one $$7$$.

2. All $$3$$s may be factors only of $$n$$ or only of $$n\+1$$ as consecutive numbers have no common factors. Same for the $$5$$s and $$7$$, so $$27$$ ($$\small =3^3 \raise.7ex\strut$$), $$25$$ ($$\small =5^2 \raise.7ex\strut$$) and $$7$$ are, in effect, indecomposable factors.

3. The possibilities of $$27$$, $$25$$ or $$7$$ being factors of a number are independent of each other because $$27$$, $$25$$ and $$7$$ share no common factors.

4. The probability that $$27$$ is a factor of $$n$$ or $$n\+1$$ is $$\f{2}{27}$$. The probability that $$25$$ is a factor of $$n$$ or $$n\+1$$ is $$\f{2}{25}$$. The probability that $$7$$ is a factor of $$n$$ or $$n\+1$$ is $$\f{2}{7}$$. As these component probabilities are independent, multiply them together for the probability that $$27$$, $$25$$ and $$7$$ are all present as factors of $$n$$($$n\+1)$$:

$$\small {2 \over 27} \x {2 \over 25} \x {2 \over 7} = {2^3 \over 27 \x 25 \x 7} = {8 \over 4725}$$

In general, the resulting probability fraction has:

• Numerator equal to 2 raised to the power that is the count of distinct prime factors of the number whose multiples are sought. (In the puzzle, $$m = 100 = \b2^2 \x \b5^2 \raise.3ex\strut$$ has $$2$$ distinct prime factors.) This is because each distinct prime factor may appear in either $$n$$ or $$n\+1$$.

• Denominator equal to the number ($$m=100$$ in the puzzle) whose multiples are sought. This is because the denominators of the multiplied component probabilities are collectively the prime factors of $$m$$ raised to their exponents.

$$\endgroup$$

If we set K=25*a, where a is an odd number, and N=(25*a±1)/4, where N is an integer, then the product K*4N is a multiple of 100.

• All odd numbers are written as 4x+3 and 4x+1 – Vassilis Parassidis May 29 at 18:28

Brute force approach(python):

def multiples_of_hundred(n):
sum = 0
for i in range(1, n + 1):
if ((i * (i+1)) % 100) == 0:
sum += 1
return sum/n


Returns 4% (0.04) for multiples of 100.

• interestingly, the maximum (when testing the first 10,000 positive integers) is 0.041666..., the value at 24. Also, the minimum, excluding the zeros before 24, is 0.0135135... at 74. – DU_ds May 29 at 2:48

My strategy is any of n or n+1 have to be divisible by 100 so that nX(n+1) becomes divisible by 100, thus 99, 100,
199, 200,
299, 300,
this way; i.e.
respectively

99X100=9900, 100X101=10100
etc.
From 101 to 198 the number of natural number is 98
Similarly from 201 to 298 " " " " " " 98

But I am worried that I might be missing some other set of numbers which may follow similar criterion as asked by OP.

Edit: As suggested by User EI Guest there are other solutions where

a factor of n and a factor of n+1 together making 100; ie

Possibility-1: n is divisible by 4 and n+1 is divisible by 5
Such as 24 and 25
as well
Possibility-2: n is divisible by 5 and n+1 is divisible by 4.
Such as 75 and 76

• This isn’t quite right — you’re missing two other solutions per 100 that work! (Namely 24x25 = 600 and 75x76 = 5700.) – El-Guest May 28 at 13:10
• @El-Guest thank you. Yes I missed that possibilities. – Always Confused May 28 at 13:11