3
$\begingroup$

I know that $\forall{a,n}\in\mathbb{Z}:\Bigl[\gcd(a,n)=1\Bigr]\implies\Bigl[\exists{k}\in\mathbb{Z}:ak\equiv1\pmod{n}\Bigr]$

In other words, for every pair of co-prime integers $a$ and $n$, there is an integer $k$ which is the inverse of $a\pmod{n}$.

Using Euclidean algorithm, I have found:

  • The inverse of $271\pmod{2015}$ is $461$
  • The inverse of $2015\pmod{271}$ is $209$

I do not understand how to apply this in the context of the question above.

I tried simplifying it in the same way but I ended up stuck and unable to find an integer $x$ such that $271x\equiv272\pmod{2015}$.

I can find many different inverses I think, but none of them are integers.

$\endgroup$
  • $\begingroup$ "How I got the answer"? It doesn't look like it's going to be you getting the answer. $\endgroup$ – barak manos Apr 8 '15 at 4:00
  • $\begingroup$ I'm just looking for help, if you notice I never explicitly asked for the answer. No need to be rude. $\endgroup$ – AndieM Apr 8 '15 at 4:02
  • 3
    $\begingroup$ Sorry, didn't mean to be rude, so I apologize. But you are usually expected to give a little more context, as well as to share your thoughts, progress and general effort made towards solving the problem on your own. $\endgroup$ – barak manos Apr 8 '15 at 4:03
  • $\begingroup$ After you've edited your question (which had been put on hold), I flagged it for a moderator and asked to reopen it. After it was reopened, I edited it myself and fixed it up with LaTex, sentence formatting, tagging, etc. Please see a couple of notes in the following comment (not enough space left in this one). $\endgroup$ – barak manos Apr 10 '15 at 7:52
  • 1
    $\begingroup$ First, I've noticed that you added a description of how you found inverses, which wasn't there before. Now, this appears to be taken directly from the answer given to you by @user3016098, so if you indeed applied it only after reading that answer, then you should at least credit that user for it. Otherwise, it is not custom to take someone else's answer and embed it into your question, because it essentially makes that answer pointless. Second, "I can find many different inverses I think, but none of them are integers" - I'm pretty sure that an inverse is integer by definition. $\endgroup$ – barak manos Apr 10 '15 at 7:52
3
$\begingroup$

Something to get you started:

The greatest common divisor of 271 and 2015 is 1, thus 271 has an inverse (mod 2015).

You may find the inverse of 271 (mod 2015) by using the Euclidean algorithm.

Multiplying both sides by this inverse will give you x equivalent to some number (mod 2015).

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Hint:

$271x\equiv272\pmod{2015}\iff$

$271x=2015n+272\iff$

$271x-271=2015n+1\iff$

$271(x-1)=2015n+1\iff$

$271y=2015n+1\iff$

$271y\equiv1\pmod{2015}$

Now simply find $y$, which is the inverse of $271\pmod{2015}$, and then calculate $x=y+1$.


Here is a piece of C code that you might find useful:

int Inverse(int n,int a)
{
    int x1 = 1;
    int x2 = 0;
    int y1 = 0;
    int y2 = 1;
    int r1 = n;
    int r2 = a;

    while (r2 != 0)
    {
        int r3 = r1%r2;
        int q3 = r1/r2;
        int x3 = x1-q3*x2;
        int y3 = y1-q3*y2;

        x1 = x2;
        x2 = x3;
        y1 = y2;
        y2 = y3;
        r1 = r2;
        r2 = r3;
    }

    return y1>0? y1:y1+n;
}

Calling Inverse(2015,271) will give you the inverse of $271\pmod{2015}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @AndieGH: You're welcome. Please see additional algorithm (depicted in C code) to help you find the inverse. $\endgroup$ – barak manos Apr 8 '15 at 4:19
0
$\begingroup$

Hint: \begin{equation*} ax\equiv b\;\left(mod\;m\right) \end{equation*} \begin{equation*} a^{-1}\cdot ax\equiv a^{-1}\cdot b\;\left(mod\;m\right) \end{equation*} \begin{equation*} x\equiv a^{-1}\cdot b\;\left(mod\;m\right) \end{equation*}

| cite | improve this answer | |
$\endgroup$

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.