+0

# number theory question on modular inverse

0
92
2

Let n be a positive integer. If $$a\equiv (3^{2n}+4)^{-1}\pmod{9}$$ , what is the remainder when a is divided by 9?

Aug 8, 2020

#1
0

No matter what the value of n is, a^(-1) mod 9 = 7

Aug 9, 2020
#2
+111628
+1

Maybe there is a quicker way to do this but here goes.

$$a\equiv (3^{2n}+4)^{-1}\pmod{9}\\ a\cdot (3^{2n}+4)\equiv 1\pmod{9}\\ a\cdot (3^{2n}+4)=9M+1\qquad \text{where M is an integer}\\ a\cdot (9^n+4)=9M+1\\ a\cdot 9^n+4a=9M+1\\ 4a-1=9M-a\cdot 9^n\\ 4a-1=9(M-a\cdot 9^{n-1})\\ 4a-1=9N \qquad \text{Where N is an integer}\\ \text{By inspection (or euclidean equation) }a=-2\;\;works\\ -2\pmod{9}\equiv 7\pmod{9}\\ a=7+9P \qquad \text{Where P is an integer}\\ \text{So if } a \text{ is divided by 9 the remainder will be 7}$$

You can check all the numbers from 1 to 8 but this is the only one of those that works.

LaTex:

a\equiv (3^{2n}+4)^{-1}\pmod{9}\\
a\cdot (3^{2n}+4)\equiv 1\pmod{9}\\
a\cdot (3^{2n}+4)=9M+1\qquad \text{where M is an integer}\\
a\cdot (9^n+4)=9M+1\\
a\cdot 9^n+4a=9M+1\\
4a-1=9M-a\cdot 9^n\\
4a-1=9(M-a\cdot 9^{n-1})\\
4a-1=9N \qquad \text{Where N is an integer}\\
\text{By inspection (or euclidean equation) }a=-2\;\;works\\
-2\pmod{9}\equiv 7\pmod{9}\\

a=7+9P  \qquad \text{Where P is an integer}\\
\text{So if a is divided by 9 the remainder will be 7}

Aug 9, 2020