1
$\begingroup$

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.

  • 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.2012-11-08
  • 0
    For starters: what part(s) of [this wiki article](http://en.wikipedia.org/wiki/Modular_multiplicative_inverse) are difficult for you to understand?2012-11-08
  • 0
    @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?2012-11-08
  • 0
    @Gerry Myerson, Yes you're right. The SomeNumber is in the range of 1 to 262012-11-08
  • 0
    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...2012-11-08
  • 0
    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?2012-11-08
  • 0
    You at least know what the greatest common divisor is (and the Euclidean algorithm), or should that be spelled out for you as well?2012-11-08
  • 0
    GCD AND Euclidean algorithm? isn't THAT algorithm used to calculate GCD?2012-11-08
  • 0
    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$...2012-11-08
  • 0
    So can you spell that out for me as an answer?2012-11-08

1 Answers 1

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$.