How to find the multiplicative inverse of $2^{29} \mod 9$

Question

I just started studying this topic and from my understanding I have to find an integer $x$ such that:

$2^{29}x \equiv 1 \mod 9$

However, I have no idea of how to find a linear combination of $9$ and $2^{29}$ given the structure of both of them.

I tried to work around with $2^{29}$ getting mods for every power but it seems like I'm going to do too many computations when I am pretty sure this could be avoided. I must be missing something, can you help me? I also tried to get a gcd, but I didn't get far.

Answer 1

As $2^3\equiv-1\pmod9,2^{29}=2^2(2^3)^9\equiv4(-1)^9\equiv-4$

So, $2^{29}x\equiv-4x\pmod9$

We need $-4x\equiv1\pmod9\iff x\equiv(-4)^{-1}$

As $-4\cdot2\equiv1\pmod9,(-4)^{-1}\equiv2$

Answer 2

$$2^{29}=4(2^3)^9\equiv 4\cdot (-1)^9\equiv -4.$$ Therefore $2$ is the inverse.

Answer 3

$2^{29}=(2^3)^9\cdot 4\equiv -4\equiv 5\mod(9)$ by Fermat's little theorem. So $2^{29}x\equiv1\mod(9)\implies 5x\equiv 1\mod(9)\implies x=2$ is an answer.

Answer 4

By Euler's Theorem

$$2^6\equiv1\pmod9$$ $$2^{30}=(2^6)^5\equiv1^5\equiv 1\pmod9$$ $$2^{29}x\equiv2^{30}\pmod9$$ $$x\equiv2\pmod9$$

Answer 5

$[2^{29}]_9$

$ = [16^7 \cdot 2]_9$

$= [7^7]_9 \cdot [2]_9$

$= [49^3]_9 \cdot [7]_9 \cdot [2]_9$

$= [4^3]_9 \cdot [14]_9$

$= [64]_9 \cdot [5]_9$

$= [1]_9 \cdot [5]_9 = [5]_9$

$[5]_9 \cdot [x]_9 = [1]_9$

$5x = 1 + 9y$

$5x - 9y = 1$

$y = 1 + 5t$

$x = 2 + 9t = [2]_9$

Answer 6

Hint $\ {\rm mod}\,\ 9\!:\,\ \color{#c00}{2^6\equiv 1}\,\Rightarrow\ \color{#0a0}2\cdot 2^{\rm\, 6\,N-1}\!\equiv (\color{#c00}{2^6})^{\rm N}\equiv \color{#c00}{1}^{\rm N}\equiv 1$

Therefore $\,\color{#0a0}2\,$ is the inverse of $\ 2^{\rm\, 6\,N-1}$ modulo $\,9.\,$ Yours is $\,N=5.$