Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.