Congruences in number theory

Question

I am working on a worksheet on number theory and I have to solve the following congruences:

$$7^{128}=n\mod 13$$ Find $n$. And $$28x^2=1\mod37$$ How should I solve these congruences? I have no clue about the first one but for the second one I suspect I should solve the quadratic equation $28x^2-1=0$.

Answer 1

For example trying a little exponents:

$$7^2=10\pmod{13}\;,\;\;7^3=7\cdot 10=5\pmod{13}\;,\;\;7^4=35=9=-4\pmod{13},$$

$$7^5=-28=-2\pmod{13}\;,\;\;7^6=-14=-1\pmod{13}$$

Thus

$$7^{128}=(7^6)^{21}\cdot7^2=(-1)^{-21}\cdot10=-10=3\pmod{13}$$

For the other one (all the time with arithmetic modulo $\;37\;$):

$$28x^2=-9x^2\implies -9x^2=1\implies x^2=-\frac19\stackrel{\text{Because}\,9\cdot4=-1}=-(-4)=4$$

and thus...

Answer 2

For the first one, by using Fermat's little theorem, we have $7^{132} = 1 \mod 13$.

So, with

$7^{128}\mod 13 = ((7^{-4}\mod 13) (7^{132}\mod 13))\mod 13$

and

$7^{-1} = 2$ in $Z_{13}$ (i.e., $2\times 7 = 1 \mod 13$)

we have $7^{128}\mod 13 = 3$.

Answer 3

As $(7,13)=1,128\equiv8\pmod{12},7^{128}\equiv7^8\pmod{13}$

Now, $7^2=49\equiv-3\pmod{13}\implies7^8=(7^2)^4\equiv(-3)^4\equiv81\equiv3\pmod{13}$