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

Discussion Overview

The discussion revolves around finding the remainder when the function $$f(100)$$, defined by a triangular array of numbers, is divided by 100. Participants explore various approaches to derive the function and its properties, including recursive relationships and modular arithmetic.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • Some participants describe a triangular array of numbers and define $$f(n)$$ as the sum of the numbers in row $$n$$.
  • One participant presents a difference equation for the sequence $$f_n$$, leading to a proposed formula $$f_n = 2(2^n - 1)$$.
  • Another participant proposes an alternative expression for $$f(n)$$ as $$2^n - 2$$, leading to calculations of $$f(100)$$ modulo 100.
  • Several participants calculate $$2^{100}$$ modulo 100 using different methods, arriving at the conclusion that $$f(100) \equiv 74 \pmod{100}$$.
  • A participant introduces the Chinese Remainder Theorem (CRT) to analyze the modular properties of $$f(100)$$, confirming the result of 74 through a systematic approach.

Areas of Agreement / Disagreement

There is no consensus on the derivation of $$f(n)$$, as participants propose different formulas and methods. However, multiple participants arrive at the same conclusion regarding the remainder when $$f(100)$$ is divided by 100, which is 74.

Contextual Notes

Some participants express uncertainty about the derivation of the formulas and the steps involved in the calculations, indicating that assumptions may vary among different approaches.

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