solving ax +b mod p = y

1,039

You have to solve $ax\equiv y-b(mod$ $p)$ the fact that $p$ is prime implies $gcd(a,p)=1$ and then the congruence $az\equiv 1 (mod$ $p)$ has a solution let $r$ be that solution.

We have $ax\equiv y-b(mod$ $p) \iff rax\equiv r(y-b)(mod$ $p)$ but $ra\equiv 1 (mod$ $p)$ so $rax\equiv x(mod$ $p)$ and the solution is $x\equiv r(y-b)(mod$ $p)$.

Share:
1,039

Related videos on Youtube

aceminer
Author by

aceminer

Updated on March 03, 2020

Comments

  • aceminer
    aceminer over 3 years

    How do I solve ax+b mod p = y, with p being prime?

    What I have gotten so far is ax = y - b (mod p)

    x = (y-b)/ (a^(p-2)) 
    

    a^p-2 being the multiplicative inverse of p. This is derived by using a^(p-1) = 1 mod p

    I solved it using Fermat little theorem but I cannot seem to get back the original $x$. Am I doing something wrong here?

    • stewbasic
      stewbasic over 6 years
      From the second to third equation you presumably multiplied by the inverse $a^{p-2}$ of $a$, so the RHS should be $(y-b)\times a^{p-2}$?
  • aceminer
    aceminer over 6 years
    So what is r? Can you give some numbers to show your answer
  • Jonathaniui
    Jonathaniui over 6 years
    Sure lets take a=7, y=4, b=2 and p=13, then you have to solve $7x \equiv 2(mod$ $13)$ the fact that $gcd(7,13)=1$ implies $7$ has an inverse $mod 13$ we calculate it and come up with $2$ and then we have $2*7x\equiv 2(2)(mod$ $13)$ and it is equal to $14x\equiv 4(mod 13)$ which is equivalent to $x\equiv 4(mod$ $13)$ and you can check that numbers of the form $13k+4$ are solutions.
  • aceminer
    aceminer over 6 years
    What is the formula for r? a^(p - 2) ?
  • Jonathaniui
    Jonathaniui over 6 years
    I don't know of any closed general formula, sorry, but I think that you can look at the order of $a$ $mod p $ and if it is $k $ then the $r$ is equal to $a^{k-1}$, in this case the order of $7$ $mod 13$ is $12$ because $12$ is the minimum number $k $ such that $7^k \equiv 1 (mod$ $13)$, now we take $7^{k-1}=7^{11}$ and we calculate $7^11\equiv 2 (mod $ $13)$ and then we have our inverse, but I don't know of a closed formula, sorry.
  • aceminer
    aceminer over 6 years
    Not a closed form but something that can be calculated programmatically will do
  • Jonathaniui
    Jonathaniui over 6 years
    Then use what I sayed in tje last comment, if $p $ is not too big you can calculate by brute force the order of an element in $\Bbb Z_p $