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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In my discrete maths homework, I'm being asked to find the inverse of a cipher function:

$$f(p) = (3p + 5) \bmod{26}$$

$f(p)$ accepts natural integers of the range ${0,1,...,25}$ (where A = $0$ and Z = $25$) and outputs in the same range.

Messing around for a lot of time, I ended up finding this function:

$$f^{-1}(p) = \Big(\frac{p + 26(p \bmod{3})}{3} + 7\Big) \bmod{26}$$

But it was obtained almost exclusively with the help of trial and error and C program I made to help me investigate, and that's not quite suitable to write on my copy.

First, is my function the best function that solves this problem? And second, how should I have found this the 'right' way?

share|cite|improve this question
up vote 2 down vote accepted

You can solve it much like you would normally. "Normally," you would like that $f^{-1}(p)=\frac{p-5}{3}$. What this means modulo $26$ is $f^{-1}(p)=\bar{3}(p-5)$, where $\bar{3}$ is the inverse of $3$ modulo $26$. But notice that $\bar{3}=9$, since $3\cdot 9\equiv 1\pmod{26}$. So $$ f^{-1}(p)=9(p-5)\equiv 9p-45\equiv 9p+7\pmod{26}. $$

share|cite|improve this answer
Thank you! (15 chars) – zneak May 26 '11 at 17:15

How would you invert if it were an ordinary equation? You'd go $x=3p+5$, $3p=x-5$, $p=3^{-1}(x-5)$, and report your answer as $f^{-1}(x)=3^{-1}(x-5)$. Well, it's the same with congruences as with equations, once you understand what $3^{-1}$ means in the context of calculations modulo 26. Do you?

share|cite|improve this answer

Your Answer


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.