# Find the remainder when f(100) is divided by by 100

#### anemone

##### MHB POTW Director
Staff member
Consider the triangular array of numbers $$\displaystyle 0,\;1,\;2,\;3,\cdots$$ along the sides and interior numbers obtained by adding the two adjacent numbers in the previoius row. Row 1 through row 6 are shown as below.

 0 1 1 2 2 2 3 4 4 3 4 7 8 7 4 5 11 15 15 11 5

Let $$\displaystyle f(n)$$ denote the sum of the numbers in row $$\displaystyle n$$. What is the remainder when $$\displaystyle f(100)$$ is divided by $$\displaystyle 100$$?

#### chisigma

##### Well-known member
Consider the triangular array of numbers $$\displaystyle 0,\;1,\;2,\;3,\cdots$$ along the sides and interior numbers obtained by adding the two adjacent numbers in the previoius row. Row 1 through row 6 are shown as below.

 1 1 2 2 2 3 4 4 3 4 7 8 7 4 5 11 15 15 11 5

Let $$\displaystyle f(n)$$ denote the sum of the numbers in row $$\displaystyle n$$. What is the remainder when $$\displaystyle f(100)$$ is divided by $$\displaystyle 100$$?
The sequence $f_{n}$ is solution of the difference equation...

$$f_{n+1} = f_{n} + 2^{n+1},\ f_{0}=0\ (1)$$

... and the solution of (1) is...

$$f_{n} = \sum_{k=1}^{n} 2^{k} = 2\ (2^{n}-1)\ (2)$$

From (2) using 'Monster Wolfram' we derive...

$$2\ (2^{100}-1)\ \text{mod}\ 100 = 50\ (3)$$

... but probably a more clever way to arrive to (3) exists...

Kind regards

$\chi$ $\sigma$

#### MarkFL

Staff member
I found by observation that:

$$\displaystyle f(n)=2\left(2^{n-1}-1 \right)$$

and hence (also using W|A):

$$\displaystyle 74\equiv f(n)\,\,\,\,(\text{mod }100)$$

Last edited:

#### Bacterius

##### Well-known member
MHB Math Helper
By observation I got $f(n) = 2^n - 2$, hence $f(100) = 2^{100} - 2$.

Now $2^5 \equiv 32 \pmod{100}$, so $2^{10} \equiv 32^2 \equiv 24 \pmod{100}$, then $2^{50} \equiv 24^5 \equiv 24 \pmod{100}$ and we conclude that $2^{100} \equiv 24^2 \equiv 76 \pmod{100}$.

Therefore $f(100) \equiv 76 - 2 \equiv 74 \pmod{100}$.

#### chisigma

##### Well-known member
Of course it is a trivial problem of indexes but it is...

$$f_{0} = 2\ (2^{0}-1) = 0$$

$$f_{1} = 2\ (2^{1}-1) = 2$$

$$f_{2} = 2\ (2^{2}-1) = 6$$

$$f_{3} = 2\ (2^{3}-1) = 14$$

... so that in general is...

$$f_{n} = 2\ (2^{n}-1)$$

Kind regards

$\chi$ $\sigma$

#### anemone

##### MHB POTW Director
Staff member
Of course it is a trivial problem of indexes but it is...

$$f_{0} = 2\ (2^{0}-1) = 0$$

$$f_{1} = 2\ (2^{1}-1) = 2$$

$$f_{2} = 2\ (2^{2}-1) = 6$$

$$f_{3} = 2\ (2^{3}-1) = 14$$

... so that in general is...

$$f_{n} = 2\ (2^{n}-1)$$

Kind regards

$\chi$ $\sigma$
Hi chisigma,

According to the general formula that you derived in the above manner, I believe f(100) is obtained when $$\displaystyle n=99$$
.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
By observation I got $f(n) = 2^n - 2$, hence $f(100) = 2^{100} - 2$.

Now $2^5 \equiv 32 \pmod{100}$, so $2^{10} \equiv 32^2 \equiv 24 \pmod{100}$, then $2^{50} \equiv 24^5 \equiv 24 \pmod{100}$ and we conclude that $2^{100} \equiv 24^2 \equiv 76 \pmod{100}$.

Therefore $f(100) \equiv 76 - 2 \equiv 74 \pmod{100}$.
Since I like the Chinese Remainder Theorem (CRT).

CRT says that the map $\psi: \mathbb Z/100\mathbb Z \to \mathbb Z/4\mathbb Z \times \mathbb Z/25\mathbb Z$ given by $\psi: x \text{ mod }{100} \mapsto (x \text{ mod }4, x \text{ mod }{25})$ is an isomorphism.

Since $\phi(25)=20$, we know from Euler's Theorem that $2^{20} \equiv 1 \pmod{25}$.
So $\psi(2^{100} - 2) \equiv (2^{100} - 2 \text{ mod }{4}, 2^{100} - 2 \text{ mod }{25}) \equiv (- 2 \text{ mod }{4}, 1^5 - 2 \text{ mod }{25}) \equiv (-2 \text{ mod }{4}, -1 \text{ mod }{25})$.

From the second argument, it follows that $2^{100} - 2$ is equivalent to one of $24, 49, 74, 99 \pmod{100}$.
Only $74$ fits with the first argument.

So $f(100) \equiv 2^{100} - 2 \equiv 74\pmod{100}. \qquad \blacksquare$