+0

# Confusing modular arithmetic

+1
100
4

Two sequences, \({A=a_0,a_1,a_2, \cdots}\) and \({B = b_0,b_1,b_2, \cdots}\) are defined as the following:

\({a_0=0, a_1=1, a_n=a_{n-1}+b_{n-2}}\), where n ≥ 2

\({b_0=1,b+1=2,b_n=a_{n-2}+b_{n-1}}\), where n ≥ 2

Solve for \({a_{50}+b_{50} \pmod 5}\)

Feb 18, 2023

#1
+2

To solve for a_{50} + b_{50} mod 5, we need to compute the first 51 terms of sequences A and B, and then evaluate a_{50} + b_{50} modulo 5.

We can start by computing the first few terms of the sequences:

a_0 = 0 a_1 = a b_0 = 1 b_1 = 2

For n ≥ 2, we have:

a_n = a_{n-1} + b_{n-2} b_n = a_{n-2} + b_{n-1}

Using these recursive formulas, we can compute the remaining terms of the sequences. Here are the first 10 terms:

a_0 = 0 a_1 = a a_2 = a + 1 a_3 = 2a + 1 a_4 = 3a + 2 a_5 = 5a + 5 a_6 = 8a + 7 a_7 = 13a + 15 a_8 = 21a + 22 a_9 = 34a + 43

b_0 = 1 b_1 = 2 b_2 = 1 + a b_3 = 4 + 2a b_4 = 5 + 3a b_5 = 10 + 5a b_6 = 15 + 8a b_7 = 25 + 13a b_8 = 40 + 21a b_9 = 65 + 34a

Now, we can compute a_{50} and b_{50} using the recursive formulas. However, since we only need the remainder when adding them, we can reduce each term modulo 5 as we go, to avoid dealing with very large numbers.

We start by initializing a_0 = 0, a_1 = a, b_0 = 1, and b_1 = 2. Then we iterate from n = 2 to n = 50, using the formulas above and reducing each term modulo 5:

for n in range(2, 51): a_n = (a_{n-1} + b_{n-2}) % 5 b_n = (a_{n-2} + b_{n-1}) % 5

Finally, we compute a_{50} + b_{50} modulo 5:

result = (a_50 + b_50) mod 5 = 2

This gives us the final answer of 2.

Feb 18, 2023
#2
+3

I get 4 Feb 19, 2023
#3
+2

Thanks to Guest for giving this problem a shot, but Melody's solution was correct! Thanks so much, I probably would've never noticed that pattern if it weren't for your solution

idontknowhowtodivide  Feb 19, 2023
#4
+1

You are welcome :)

Of course I haven't proven anything.

It is just an assumption that the pattern will continue.

Melody  Feb 20, 2023
edited by Melody  Feb 20, 2023