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

  • Context: MHB 
  • Thread starter Thread starter anemone
  • Start date Start date
  • Tags Tags
    Remainder
Click For Summary
SUMMARY

The remainder when \( f(100) \) is divided by 100 is 74. The function \( f(n) \) is defined as \( f(n) = 2(2^n - 1) \), derived from the difference equation \( f_{n+1} = f_n + 2^{n+1} \) with \( f_0 = 0 \). By applying modular arithmetic and the Chinese Remainder Theorem, the calculations confirm that \( 2^{100} \equiv 76 \mod 100 \), leading to \( f(100) \equiv 74 \mod 100 \).

PREREQUISITES
  • Understanding of modular arithmetic
  • Familiarity with difference equations
  • Knowledge of the Chinese Remainder Theorem
  • Basic concepts of exponential functions
NEXT STEPS
  • Study the properties of modular arithmetic in depth
  • Learn about solving difference equations
  • Explore the applications of the Chinese Remainder Theorem
  • Investigate exponential growth and its implications in number theory
USEFUL FOR

Mathematicians, students studying number theory, educators teaching modular arithmetic, and anyone interested in combinatorial mathematics.

anemone
Gold Member
MHB
POTW Director
Messages
3,851
Reaction score
115
Consider the triangular array of numbers $$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.

[TABLE="width: 500"]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]0[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]1[/TD]
[TD][/TD]
[TD]1[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]2[/TD]
[TD][/TD]
[TD]2[/TD]
[TD][/TD]
[TD]2[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD]3[/TD]
[TD][/TD]
[TD]4[/TD]
[TD][/TD]
[TD]4[/TD]
[TD][/TD]
[TD]3[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD]4[/TD]
[TD][/TD]
[TD]7[/TD]
[TD][/TD]
[TD]8[/TD]
[TD][/TD]
[TD]7[/TD]
[TD][/TD]
[TD]4[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]5[/TD]
[TD][/TD]
[TD]11[/TD]
[TD][/TD]
[TD]15[/TD]
[TD][/TD]
[TD]15[/TD]
[TD][/TD]
[TD]11[/TD]
[TD][/TD]
[TD]5[/TD]
[/TR]
[/TABLE]

Let $$f(n)$$ denote the sum of the numbers in row $$n$$. What is the remainder when $$f(100)$$ is divided by $$100$$?
 
Mathematics news on Phys.org
anemone said:
Consider the triangular array of numbers $$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.

[TABLE="width: 500"]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]1
[/TD]
[TD][/TD]
[TD]1
[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]2
[/TD]
[TD][/TD]
[TD]2
[/TD]
[TD][/TD]
[TD]2
[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD]3
[/TD]
[TD][/TD]
[TD]4
[/TD]
[TD][/TD]
[TD]4
[/TD]
[TD][/TD]
[TD]3
[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD]4
[/TD]
[TD][/TD]
[TD]7
[/TD]
[TD][/TD]
[TD]8
[/TD]
[TD][/TD]
[TD]7
[/TD]
[TD][/TD]
[TD]4
[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]5
[/TD]
[TD][/TD]
[TD]11
[/TD]
[TD][/TD]
[TD]15
[/TD]
[TD][/TD]
[TD]15
[/TD]
[TD][/TD]
[TD]11
[/TD]
[TD][/TD]
[TD]5
[/TD]
[/TR]
[/TABLE]

Let $$f(n)$$ denote the sum of the numbers in row $$n$$. What is the remainder when $$f(100)$$ is divided by $$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$
 
I found by observation that:

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

and hence (also using W|A):

$$74\equiv f(n)\,\,\,\,(\text{mod }100)$$
 
Last edited:
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}$.
 
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$
 
chisigma said:
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 $$n=99$$.
 
Bacterius said:
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$
 

Similar threads

MHB Divisibility of (1!+2!+3!+...+100!)^2 by 5
  • · Replies 1 ·
Replies
1
Views
1K
MHB What is the remainder when m+n is divided by 1000 in a trigonometric challenge?
  • · Replies 2 ·
Replies
2
Views
1K
MHB Find remainder when (2∗4∗6∗8⋯∗2016)−(1∗3∗5∗7⋯∗2015) is divided by 2017
  • · Replies 2 ·
Replies
2
Views
2K
MHB Find Remainder of $2^{100}-1$ Divided by 1000
  • · Replies 1 ·
Replies
1
Views
3K
MHB Find Remainder When Divided by 19
  • · Replies 2 ·
Replies
2
Views
2K
MHB Find Polynomial Given Remainder After Division
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad Remainders, need Help proving a simple notion
  • · Replies 3 ·
Replies
3
Views
1K
What is the remainder when the following sum is divided by 4?
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Not a trained mathematician, but this seems to work consistently
  • · Replies 9 ·
Replies
9
Views
2K
Find the remainder when ## 4444^{4444} ## is divided by ## 9 ##.
  • · Replies 3 ·
Replies
3
Views
2K