0
$\begingroup$

I've been trying to study on my own, the relationship between 2 numbers as you move down the number line from a starting point and could use some help. I believe this could be described as modular arithmetic, but I've been struggling to understand that logic - so please forgive me if this question is rudimentary.

Say that you have 2 prime numbers, 61 and 17 and we imagine that you are at "61" on the number line. At this moment in time, 17 has a modulo value of 10 (61 mod 17).

Let's add 61 .. bringing us to 122. So what happened at (mod) 17? Well, ignoring the fact we could do 122 mod 17, we could just add 10 again to yield 20. BUT, 20 is 3 more than 17, so with the wrap-around we landed at 3. Let's call this answer M

Now this is of course no great revelation.. however, what I can't figure out on my own, is how to arbitrarily yield a given M

Say I want to continue adding values to 61 .. I want to reach M = 14

or when is
61 * x mod 17 = 14

So from the below table I created, the answer for x = 15. And this process seams to follow a pattern of sorts, because I used 2 prime numbers I know that each point along 17 will be hit along the line until we've added 61 17 times, at which point the pattern repeats.

So:

Could I have used a formula of some kind to arrive at 15? And if so, would that method differ for composite numbers?

Thanks for helping a novice..

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ Since you are solving $61x\equiv 14 \pmod{17}$, you will need the multiplicative inverse of $61 \mod 17$. $\endgroup$
    – John Habert
    Feb 18, 2014 at 3:44
  • $\begingroup$ Thank you, I came across that concept today in my research but wasn't sure how to proceed since it's not in the form a ≡ 1(mod17) (my formula has 14).. I need help seeing all of the steps please @John Habert $\endgroup$
    – LaloInDublin
    Feb 18, 2014 at 3:51

1 Answer 1

Reset to default
1
$\begingroup$

Let's say you are solving the basic algebra equation $3x=15$. To get $x$ by itself, you multiply both sides by the inverse of $3$, which is $\dfrac{1}{3}$ (we usually view this as dividing by $3$ instead of multiplying by $\dfrac{1}{3}$ but they are the same thing). To solve $61x \equiv 14 \pmod{17}$, you need to do the same thing. We need to multiply by a number to get rid of the $61$. Hence you need to find the number $y$ such that $61y \equiv 1 \pmod{17}$. Using either method here, you find that $61*12 \equiv 1 \pmod{17}$. So you get that $61x \equiv 14 \pmod{17} \iff 12*61x\equiv 12*14 \pmod{17} \iff x \equiv 168 \pmod{17} \iff x \equiv 15 \pmod{17}$.

$\endgroup$
2
  • $\begingroup$ Thank you very much! Been struggling with this question for a long time, wondering how to write something like this method. (As a reference to others I had to watch this video to better understand finding the Modular inverse ) youtube.com/watch?v=shaQZg8bqUM $\endgroup$
    – LaloInDublin
    Feb 18, 2014 at 4:39
  • 1
    $\begingroup$ You're welcome. For those coming later, the video uses the extended Euclidean algorithm to find the inverse. $\endgroup$
    – John Habert
    Feb 18, 2014 at 4:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .