How to solve $\,a^{100}\equiv 2,\ a^{101}\equiv 69\pmod{73}$

Question

If I know that $a^{100}\equiv 2\pmod{73}$, $a^{101}\equiv 69\pmod{73}$

then find $a\equiv x\pmod{73}$

I can write $a^{101}\equiv a^{100+1}\equiv 2x\equiv 69 $, then $x\equiv 71\pmod{73}$ I am not so sure is this ok?

Answer 1

It's correct, but we must justify $\,2x\equiv 69\iff x\equiv 71\pmod{\!73}\,$ and also verify the root.

$\quad \bmod 73\!:\,\ \color{#0a0}{a^{100}\equiv 2}\ \Rightarrow\ 69\equiv \color{#0a0}{a^{100}} a\equiv \color{#0a0}2a\!\iff\! 2a\equiv 69\equiv -4 \color{#c00}{\!\iff\!} a\equiv -2\equiv 71$

It's valid to $\color{#c00}{{\rm cancel}\ 2}\,$ since, by Bezout, elements coprime to $73$ are invertible so cancellable (by multiplying by the inverse). Because our first arrow $(\Rightarrow)$ is unidirectional, we need to verify it reverses, i.e. $\,a\equiv -2\,$ satisfies $\,a^{100}\equiv 2.\,$ i.e. $\, (-2)^{100}\equiv 2,\,$ which is true iff $\,2^{99}\equiv 1,\,$ again by cancelling $2.\,$ Let $n$ be the order of $2.\,$ By Fermat $\,2^{72}\equiv 1\,$ so $\,n\mid 72.\,$ Therefore

$$\,2^{99}\equiv 1\iff n\mid 99\iff n\mid 99,72\iff n\mid (99,72)=9(11,8)=9\iff 2^9\equiv 1\qquad$$

which is true: $\, 2^9\equiv 2^3 2^6\equiv 8(-9)\equiv 1.\,$ So $\,a\equiv -2\,$ is the unique solution of the congruences.

Remark $ $ Alternatively we can employ the above modular calculations within a Euclidean gcd calculation, using the gcd property $\,(x,y) = (x,\,y\bmod x)$ as sketched below for any odd $n$

$$\begin{align} &\ \ n\mid a^{101}\!+\!4,\,a^{100}\!-2\\[.3em] \iff\, n = &\ (n,\,a^{101}\!+\!4,\,a^{100}\!-2)\\ =&\ (n,\ 2a\, +\, 4,\,a^{100}\!-2)\\ =&\ (n,\ \ \,a\ +\, 2,\,a^{100}\!-2)\ \ \ {\rm by}\ \ (n,2)=1\ \ \\ =&\ (n,\ \ \, a\,+\ 2,\,(-\!2)^{100}\!-2)\\[.3em] \iff\qquad &n\, \mid \ \ \, a\,+\ 2,\,(-\!2)^{100}-2\end{align}\qquad\qquad $$

Answer 2

==== 2nd answer that assumes some basic knowledge of modular arithmetic====

As $73$ is prime every equivalence class (except $0$) has a multiplicative inverse and we can solve by equations by division.

So if $a^{100}\equiv 2 \pmod{73}$ and $a^{101} \equiv 69\pmod{73}$ then $a \equiv 69*2^{-1}\equiv (-4)*2^{-1}\equiv -2\pmod {73}$.

But this assumes that $a^{100} \equiv 2 \pmod{73}$ and $a^{101}\equiv 69\pmod {73}$ has a solution in the first place.

[Notice if we said $a^{k}\equiv 2; a^{k+1}\equiv 69$ for any $k$ we'd have gotten the same answer even though it's obviously not true that $(-2)^k \equiv 2$ for all $k$.]

If $(-2)^{100} \equiv 2$ then $(-2)^{99} \equiv -1$ and $(-2)^{198}\equiv 1$. By Fermat's Little Theorem $(-2)^{72}\equiv 1 \pmod {73}$ so if $(-2)^{198} \equiv 1$ then $(-2)^{\gcd(198, 72) = 18} \equiv 1$. This would implies $(-2)^9 \equiv \pm 1$. And as $2^{99} \equiv -1$ this would mean $(-2)^9 \equiv -1 \pmod {73}$.

Well, does it? $(-2)^9 = -512= -1 - 7*73 \equiv -1 \pmod {73}$.

Thus $(-2)^{99} =((-2)^9)^{11} \equiv (-1)^{11} \equiv -1 \pmod {73}$ and so $a^{100}\equiv -1*-2\equiv 2$ and $a^{101}\equiv 2*(-2)\equiv -4 \equiv 69 \pmod {73}$.

=== first answer which assumes little knowledge of modular arithmetic; but assumes the conditions as given (that $a^{100}\equiv 2$ even has a solution and that such a solution would be compatible with $a^{101}\equiv 69$) were God's truth on earth. ===

$a^{101} = a^{100}\cdot a \equiv (\text{anything that }a^{100}\text{ is equivalent to})\cdot (\text{anything that }a\text{ is equivalent to})\equiv 2\cdot x \pmod {73}$.

And $a^{101}\equiv 69\pmod {73}$. So $2x \equiv 69 \pmod {73}$ is a correct statement. That is what you must solve.

You claim out of the blue that $x \equiv 71 \pmod {73}$ but don't expain why.

Well, one intuitive way I can see is $2x \equiv 69 \equiv -4\pmod {73}$ so $x \equiv -2$ or $x \equiv 71 \pmod {73}$ seems a good way of figuring out.

But I have to wonder is $x \equiv 71 \pmod{73}$ then only answer. For example if I had $2*x \equiv 2 \pmod{10}$ then $x \equiv 1 \pmod {10}$ is one answer but $x \equiv 6 \pmod {10}$ is another.

So $2x \equiv 69 \pmod {73}$ means there is an integer $k$ so that $2x = 69 + 73k$. So $x = \frac {69 + 73k}2$. The only way this is possible is if $69 + 73k$ is even which would mean $k$ is odd. So there is an $m$ so that $k = 2m + 1$ and $x = \frac {69 + 73(2m + 1)}2 = \frac {69+73}2 + 73m = 71 + 73m$ so $x \equiv 71 \pmod{73}$ and that is unique.

[I guess another way of doing $2x \equiv 69 \pmod {73}$ is $2x \equiv 69 \equiv 69+73 \equiv 142 \pmod{73}$ and $x \equiv 71 \pmod{73}$ is a solution.

If we tried to do that with $2x \equiv 2 \pmod {10}$ we'd have there is an $k$ so that $2x = 2 + 10k$ so $x = 1 + 5k$. We don't know if $k$ is even or odd. Let $k = 2m + i$ where $i$ might be either $1$ or $0$. Then $x = 1 + 5(2m + i) = (1 + 5i) + 10m$ so $x \equiv 1 + 5i \pmod{10}$ where if $i =0$ we have $x \equiv 1 \pmod{10}$ and if $i = 1$ we have $x \equiv 6 \pmod{10}$ so those are the two answers.

====

So food for thought.

Sometimes you can do $mx \equiv k \pmod{n}$ so $x \equiv \frac {k + j*n}n \pmod {n}$ for some $j$ to get all solutions.... and sometimes you can't. Do you have any idea when you can and when you can not?