1

I'm very curious about this cause I saw it done, but can't understand how and here it goes:

PrimeNumber * SomeNumber % 26

Now if I know the prime number, and the 26 And the result, can I find the "SomeNumber"? Thanks

Edit: I'm not good with math, so a simple explanation without fancy symbols would be appreciated.

Not Amused
  • 113
  • 1
    If the prime number is 13, and the result is zero, the "some number" could be 0, or 2, or 4, or 6, .... For other (odd) primes, it's not that bad, but, still, you have to also know that "some number" is between 1 and 26, inclusive, in order to get a unique answer. – Gerry Myerson Nov 08 '12 at 05:47
  • For starters: what part(s) of this wiki article are difficult for you to understand? – J. M. ain't a mathematician Nov 08 '12 at 05:47
  • @J.M. For starters: what part of "I'm not good with math, so a simple explanation without fancy symbols would be appreciated." is difficult for you to understand? – Not Amused Nov 08 '12 at 05:50
  • @Gerry Myerson, Yes you're right. The SomeNumber is in the range of 1 to 26 – Not Amused Nov 08 '12 at 05:51
  • I'm trying to gauge how much modular arithmetic you know (and thus, I'm asking you which parts of the article have to be explained in words to you), since you're bent on dealing with it, but, if we're going to be snippy and make things tougher, well... – J. M. ain't a mathematician Nov 08 '12 at 05:53
  • I can understand stuff, at least I know how modulus works. But I know all I know with code not math symbols. All those α, β, χ, y, Σ ... can we skip those? – Not Amused Nov 08 '12 at 05:57
  • You at least know what the greatest common divisor is (and the Euclidean algorithm), or should that be spelled out for you as well? – J. M. ain't a mathematician Nov 08 '12 at 05:58
  • GCD AND Euclidean algorithm? isn't THAT algorithm used to calculate GCD? – Not Amused Nov 08 '12 at 06:04
  • Yes, you use the Euclidean algorithm to calculate the greatest common divisor. The upshot is that it can also be used to solve this problem you have, for as long as your prime number is not $2$ or $13$, which happen to be factors of $26$... – J. M. ain't a mathematician Nov 08 '12 at 06:07
  • So can you spell that out for me as an answer? – Not Amused Nov 08 '12 at 06:12

1 Answers1

1

In general, if $\gcd(a,m)=1$, then $$ax\equiv b\pmod m$$ has a unique solution $x$ satisfying $1\le x\le m$, and this solution can be computed efficiently by use of the extended Euclidean algorithm, which see.

In your situation, where $m=26$, and $a$ is a prime number, the condition $\gcd(a.m)=1$ is guaranteed, unless $a=2$ or $a=13$.

Gerry Myerson
  • 179,216