3
$\begingroup$

I am a student who is struggling terribly with Discrete Mathematics 2. I've already changed my major from computer science to IT because it's just not a great fit for me but I'd still like to leave this course with some knowledge seeing as I've spent a great deal of money on college to begin with.

I am having trouble understanding modular arithmetic and I have to solve these two problems by hand:

$$89 ^ {307} \bmod 713$$

$$49 ^ {307} \bmod 713$$

If anyone could show me how to even approach this I'd be thankful. My class is learning through theorems which isn't helpful at all. I need this to be broken down like it's being taught to a 3 year old. Thank you for your help in advanced.

$\endgroup$
  • 2
    $\begingroup$ khanacademy.org/computing/computer-science/cryptography/… $\endgroup$ – user204299 Oct 30 '15 at 22:40
  • $\begingroup$ What do you mean with "by hand"? Can you specify which operations are permitted? Your teacher sounds a bit sadistic... $\endgroup$ – A.P. Oct 31 '15 at 0:08
  • $\begingroup$ @A.P. this doesn't take all that much computation given a few tricks-see below. Without the tricks, well... $\endgroup$ – Kevin Carlson Oct 31 '15 at 0:30
3
$\begingroup$

Start by factoring into primes, $713=23\times 31$. We'll first find $89^{307}$ modulo $23$ and $31$, and combine those answers to get the final one. Modulo $23$, $89$ is equivalent to $-3$, since it's $4*23-3$. So we're calculating $(-3)^{307}$ modulo $23$.

Now you need to use one of these theorems, namely "Fermat's little theorem," which says that $n^{p-1}\equiv 1\pmod p$ for any prime $p$. That tells us that $(-3)^{22}\equiv 1 \pmod{23}$, in this case. Then $(-3)^{44}=((-3)^{22})^2\equiv 1^2\pmod{23}$, and similarly for bigger multiples of $22$: this leads to the common strategy in problems like this of cancelling out multiples of $p-1$ from the power we're taking. That is, since $307=308-1$ and $308$ is a multiple of $22$, $(-3)^{301}\equiv (-3)^{-1}\pmod{23}$. So we have to find the multiplicative inverse of $-3\pmod{23}$, i.e. we need $x,y$ so $-3x+23y=1$. We have $2=23+7(-3)$ and $1=-3+2*2$, so $-3x+23y=-3+2*2=-3+2(23+7(-3))=15(-3)+2(23)$, which shows $15$ is the inverse of $-3$ modulo $23$. What I've done here is run the Euclidean algorithm backwards-if you don't know the algorithm you'd better look it up.

Now, modulo $31$, we're doing $89\equiv -4$ to the $307\equiv 7$, and here we basically just calculate directly: $(-4)^7=(-4)(-4)^2(-4)^4\equiv (-4)(-15)(8)\equiv 15(\pmod{31})$. So, $89^{307}$ is $15$ modulo both $23$ and $31$, and so it's also $15$ modulo $713$! This follows from another theorem, usually called the Chinese Remainder theorem.

$\endgroup$
  • $\begingroup$ Just to clarify my comment: of course I looked at the CRT and Fermat's little theorem! The whole computation would have flown fairly well for me -- although maybe it would have taken me a bit longer to find the multiplicative inverse of $-3$ modulo $23$ -- if it weren't for the very first step. Maybe you have some trick for it, but factoring $713$ by hand is almost too computational heavy for me to do by hand, even though I do have a master's degree in mathematics... :P $\endgroup$ – A.P. Oct 31 '15 at 1:05
  • 1
    $\begingroup$ Factoring 713, @A.P.? You can see at a glance that it’s not divisible by any prime less than $17$. For that prime, add $713+17=730$, $73+17=90$, so not divisible by $17$; for $19$, add $57$ to get $760$, so not divisible by $19$. Subtract $23$ from $713$ and get $690=30\cdot23$, so there’s your factorization. No pencil. $\endgroup$ – Lubin Oct 31 '15 at 5:09
  • $\begingroup$ @Lubin a nice technique! $\endgroup$ – Kevin Carlson Oct 31 '15 at 14:53
1
$\begingroup$

Two tools are required for this kind of problems: the Chinese remainder theorem, which is used to solve systems of simultaneous congruences via Bézout's identity, and the little Fermat's theorem. I'll try to show from the first problem.

First, as $713=23\cdot 31$ and the factors are (co)prime, $\;\mathbf Z/713\mathbf Z\simeq \mathbf Z/23\mathbf Z\times \mathbf Z/31\mathbf Z$. The interesting isomorphism is from right to left: if you have a pair of congruence classes: $\alpha\pmod{23}$ and $\beta \pmod{31}$, it corresponds to the congruence class of $$ 23u\beta+31v\alpha\mod 23\cdot31, $$ where $u$ and $v$ are the coefficients of a Bézout's identity between $23$ and $31$, say $$ -4\cdot 23+3\cdot 31=1. \tag{1}$$ Now as $89\equiv 20\mod23$, we have $89^{307}\equiv 20^{307}\mod 23$. Furthermore, by Little Fermat, $20^{22}\equiv 1\mod23$, so $20^{307}\equiv 20^{307\bmod22}=20^{-1}\mod23$.

We find the inverse of $20\bmod23$ with Bézout' identity: $$7\cdot 23-8\cdot 20=1$$ which shows $\;20^{-1}\equiv-8\equiv\color{red}{15}\mod23$.

Similarly, $89\equiv -4\mod31$, and $$89^{307}\equiv -4^{307\bmod30}=-4^7=-2^{14}\mod31.$$ Furthermore, $2^5\equiv 1\mod 31$, hence $$89^{307}\equiv -2^{-1}\equiv \color{blue}{15}\mod31. $$

Thus we have to solve the system of congruences $\;\begin{cases}x\equiv 15\mod23\\ x\equiv15\mod31\end{cases}$. We just have to apply formula $(1)$: $$x\equiv-\color{blue}{15}\cdot4\cdot23+\color{red}{15}\cdot3\cdot31\equiv15\mod713.$$

$\endgroup$
  • $\begingroup$ I fixed a couple of typos for you. Hope you don't mind... $\endgroup$ – A.P. Oct 31 '15 at 1:11
  • 1
    $\begingroup$ @AP.:Not at all. I know I should re-read what I write more carefully. Thanks! $\endgroup$ – Bernard Oct 31 '15 at 1:15
  • $\begingroup$ Where you find the inverse of 30 mod 23 with Bezout' Identity, where does the 7 multiplied by 23 and the 8 multiplied by 20 come from? $\endgroup$ – user2101463 Oct 31 '15 at 2:43
  • $\begingroup$ It comes from the extended Euclidean algorithm. You'll find an example of how it runs in an answer to this question $\endgroup$ – Bernard Oct 31 '15 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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