Take the 2-minute tour ×
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.

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.

share|improve this question
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 8 '12 at 5:47
    
For starters: what part(s) of this wiki article are difficult for you to understand? –  J. M. Nov 8 '12 at 5: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? –  Deus Deceit Nov 8 '12 at 5:50
    
@Gerry Myerson, Yes you're right. The SomeNumber is in the range of 1 to 26 –  Deus Deceit Nov 8 '12 at 5: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. Nov 8 '12 at 5:53
show 5 more comments

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

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.