1

I used the following formula to answer the question;

$$\frac{((x∗k)+1)}{n},$$

where $x=(1,2,3...N)$. If the result of the formula is an integer then that result is the inverse to n mod k. In this case n=5 and k=26. So I found that when $x=1$ the result is $5.4$. When $x=2$ the result is $10.6$. When $x=3$ the result is $15.8$. When $x=4$ the result is $21$. 21 is an integer so $5∗21=1 \space mod\space 26.$

Can anyone explain whether $N=26$ in this case, because we are dealing with Mod $26$?

Jnyeboah93
  • 541
  • 1
    I think that you need to get a deeper understanding of the topic (which goes far beyond the simple memorisation of facts and formulae). So, I would advise you to read a good book on number theory (please, feel free to ask for some references). Besides, you can find many lecture notes available for free online (again, feel free to ask for references). –  Oct 08 '14 at 15:30

3 Answers3

3

Yes, $N=26$ in your case, and in general $N=k$ in your algorithm.

On a side remark, you could have quickly noticed that $5\times 5 \equiv 25 \equiv -1$ so $5 \times (-5) \equiv 1$ mod $26$.

On the general case I would recommend using the extended Euclidean algorithm rather than the method you described for calculating inverses as it is significantly faster and deep.

Chocosup
  • 631
  • 3
  • 6
  • I thought when you multiply a number by its inverse you should only get 1. When you do $5×5≡25≡−1 \space mod \space 26$, can you use -1 because we are looking at the magnitude of the number and not the sign of it? – Jnyeboah93 Oct 08 '14 at 15:01
  • No, I just state that if $5 \times a \equiv -1$, then $5 \times (-a) \equiv 1$ so the inverse of $5$ is $-a$. It's just a trick using that I immediately saw $26 = 5\times 5 + 1$. Also, there is no magnitude with residues. – Chocosup Oct 08 '14 at 15:08
  • I don't think $N=26$ here. You don't have to go that high. Please see my post. – Deepak Oct 08 '14 at 15:14
  • 1
    Oh, you're actually right. I didn't really see the purpose of this bruteforce algorithm and was too focused on Euclid algorithm so I didn't try hard enough to understand... – Chocosup Oct 08 '14 at 15:22
0

To find the modular multiplicative inverse x of 5(mod 26), you must solve the equation

x = 5^(-1)(mod 26)

5x = 1(mod 26)

5x = 105(mod 26)

x = 21(mod 26)

The inverse is 21. If you multiply a number by its inverse, you get 1.

21*5 = 105, but 105(mod 26) = 1.

John Butnor
  • 74
0

No, $N \neq 26$ in your example.

Every number $n$ coprime to the modulus $k$ has exactly one unique inverse $i$ in the range $1 \leq i \leq k-1$.

Imposing those bounds, we get:

$$1 \leq \frac{xk + 1}{n} \leq k-1$$

$$\lceil \frac{n-1}{k}\rceil \leq x \leq \lfloor\frac{n(k-1)-1}{k}\rfloor$$

So in your case, you only had to test $x = 1, 2, 3, 4$.

To make things slightly simpler, you can just take the lower bound as $1$ and the upper bound as $n$. This will be fine for small values of $n$, where you don't do too much "extra" work.

I would point you toward the Extended Euclidean Algorithm as a much more efficient way of calculating the modular inverse. A nice implementation is the 'magic box' method.

Deepak
  • 26,801