0

Two sequences of integer numbers $a_n$ and $b_n$ satisfy the following conditions: $$a_1=1$$ $$b_1=2$$ $$a_{n+1} ≡ 5a_n + 1 \ (\text{mod}\ 2022)$$ $$b_{n+1} ≡ 5b_n + 1 \ (\text{mod}\ 2022)$$

for all integer n ≥ 1.

Show that for all $n ∈ Z^+$, $$a_n ≢ b_n \ (\text{mod}\ 2022)$$

I've computed the first few results for n, noticing that $a_n$ = $b_n$ - $5^{n-1}$

I've also tried to start a proof by contradiction, deducing that if the statement was true then

$$5a_{n-1}+1 ≡ 5b_{n-1}+1\ (\text{mod}\ 2022)$$ $$5a_{n-1} ≡ 5b_{n-1}\ (\text{mod}\ 2022)$$

I'm stuck here though.

1 Answers1

1

Edit: Based on your edit, in your proof of contradiction, try using the fact that $(5,2022)=1$ or simply that $5$ is prime.

ANSWER:

Suppose there was a $n$ such that $a_n\equiv b_n\mod 2022;$ then, it follows that \begin{align}5a_{n-1}+1&\equiv a_n\mod 2022\\&\equiv b_n\mod 2022 \\ &\equiv 5b_{n-1}+1\mod 2022.\end{align}

This would mean that $b_{n-1}\equiv a_{n-1}\mod 2022$ and so, by induction we have for all $n,$ $a_n\equiv b_n\mod 2022$; this is a contradiction as $a_1\not\equiv b_1\mod 2022$.

PCeltide
  • 1,534
  • I follow along up until the induction part and then I'm not really sure what you've deduced. Is it just that because the base case fails (i.e n=1) that the congruency is false? How does that prove the statement false for all n though? –  Sep 08 '22 at 07:32
  • So, if there is a $n$ for which the congruence is true, it follows that it must be true for all positive integers less than $n$ as well; this is a contradiction as it is not the case for $n=1$. – PCeltide Sep 08 '22 at 07:41
  • oh that explanation makes a lot more sense, thank you! –  Sep 08 '22 at 07:45