Welcome to our community

Be a part of something great, join today!

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

  • Thread starter
  • Admin
  • #1

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,680
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
11
222
3443
47874
5111515115

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
Feb 13, 2012
1,704
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

Administrator
Staff member
Feb 24, 2012
13,775
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
Jan 26, 2012
644
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
Feb 13, 2012
1,704
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$
 
  • Thread starter
  • Admin
  • #6

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,680
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
Mar 5, 2012
8,776
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). (Inlove)


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$