# Baby step Giant Step Help

Hey guys need a bit of help. My online lecture for this topic is missing audio so I got a little stuck.

Basically I don't know how to simplify $5\cdot3^{-16}$ They have $5\cdot3^{-16} = 5 \mod 7$

Below is the whole example in case you need context: Solve $3^x = 5 \mod 7$

Baby Step $3^0=1, 3^1=3, 3^2=2, 3^3=6$

Giant Step $5\cdot3^0=5, 5\cdot3^{-4}=3, 5\cdot3^{-8}=6, 5\cdot3^{-16}=5$

Matches $3^1 = 5\cdot3^{-4}$ and $3^3=5\cdot3^{-8}$

Answer: $3^5 = 5$ and $3^{11}=5 \mod 7$

I get the whole process except how to simplify the likes of $5\cdot3^{-16}=5$

Any help would be awesome. Thanks

-

You want to solve $3^x \equiv 5 \mod 7$. Your "baby steps" got you a few powers of $3$: $$3^0 \equiv 1, \ 3^1 \equiv 3,\ 3^2 \equiv 2,\ 3^3 \equiv 6$$ but none of those is $5$. But multiply each of those by $5$:

$5 \times 3^0 \equiv 5 \times 1 \equiv 5$ is not really a help.

$5 \times 3^1 \equiv 5 \times 3 \equiv 1 \equiv 3^0$

Ah, that's useful: so $5 \equiv 3^0/3^1 \equiv 3^{-1}$.

Ah, but you want positive $x$, not negative. Well, $3^3 \equiv 6 \equiv -1$ so $3^6 \equiv (3^3)^2 \equiv 1$. And then for any integer $x$ (positive or negative), $3^x = 3^{x+6}$. So the positive integer answers are $$x = -1 + 6 = 5,\; 5 + 6 = 11,\; 11 + 6 = 17, \ldots$$

EDIT: For $13^x \equiv 5 \mod 37$, you might do something like this. \eqalign{13^2 &\equiv 21 \equiv -16\cr 13^4 &\equiv 34 \equiv -3\cr 13^8 &\equiv 9 \equiv -28\cr 13^{16} &\equiv 7 \equiv -30\cr 13^{32} &\equiv 12 \equiv -25\cr} Well, $3 \equiv 21/7 \equiv 13^2/13^{16} \equiv 13^{-14}$ But then $-1 = (-3)/3 \equiv 13^{4 - (-14)} \equiv 13^{18}$ and $1 \equiv (-1)^2 \equiv 13^{36}$ (but you might already know this from Fermat's theorem). Now $25 \equiv (-1)(-25) \equiv 13^{18 + 32} \equiv 13^{50}$. And $13^{25}$ is a square root of that, so either $5$ or $-5$. As it turns out, $13^{25} \equiv 13^{16+8+1} \equiv 5$.

-
Ok but what about if it were solve 13^x = 5 mod 37 then with 7 steps there are no matches. i guess thats why my lecture wanted larger steps? –  Ryan Oct 23 '13 at 4:17