Calling people good at math.

[nevertoobig]

I have a friend who needs the answer to the question below about modular arithmetic quite urgently. If anyone could help it would be greatly appreciated.


The question is posted below, completely in his own words.

----------------------------
Question
----------------------------


Is there any 'slick' algorithm, using input values a, b and n, that will find x(modn) as the solution of the equation

ax = b(modn) ?

For example, if 8x = 5(mod13), (i.e. a=8, b=5 and n=13), then we need a number that, when multiplied by 8 in modulo 13 arithmetic, will 'reduce' to 5, i.e. 8x must be of the form 13.p+5 where p is an integer. The answer is x=12(mod13) because then
8x=96(mod13)=5(mod13) since 96=13.7+5 (p=7). Can I use some general algorithm with the numbers 8, 5 and 13 as inputs, that will quickly yield the answer 12?

The only way I seem to be able to do this sort of problem is by the method(s) outlined below, which seem a bit unsophisticated to me. It also occurs to me that, if n is a very large prime, as I understand is the case in cryptography, then there would be a lot of work to do by my mundane method! Is this where a computer comes in? Has any of this anything to do with Euclid's algorithm? If so, what's the connection?

I can only solve the problem 8x=5(mod13) by repeatedly adding 13 onto 5, and checking to see if the result is a multiple of 8. I eventually get to 96 (= 13.7+5, so p=7), and 96 = 8.12 of course. Hence 8x=96(mod13) from which it follows that x=12(mod13). Checking the correctness of this is straightforward by the inverse process 8.12(mod13)=96(mod13)=5(mod13). Alternatively, one might just spot that
5(mod13)= -8(mod13), so that x=-1(mod13)=12(mod13) which is a bit quicker, but why should this be a more obvious way? Just because it is quicker? Surely it's only a question of whether to go clockwise or anti-clockwise around the 13 digit clock, and what if the question is such that the answer is slap bang in the middle of the clock?

For example, solving 8x=4(mod13) yields x=7(mod13) since
4(mod13)=56(mod13) by adding 4 lots of 13 onto 4, or
x=-6(mod13)=7(mod13) since 4(mod13)= -48(mod13) by subtracting 4 lots of 13 from 4 ! No advantage gained using my iterative method. So is there a slick way in which the inputs 8, 4 and 13 in this case can yield the required output of 7?

 

[PoyeBoy]

Bumped for no appearant fucking reason

 

[MassiveGunz]

holy

bro im not that good at mod arithmatics(maybe ask wodin or velvit> but once i get that mod job i should be lot mor help on problems lik this

im thinkin its x > (#

?

but i dunno bor im not that good at fraktions

im gettin a beer its lookin lik theres some good chattin goin on tonite

 

[The Shadow]

lol

 

[MattTheSkywalker]

I can only solve the problem 8x=5(mod13) by repeatedly adding 13 onto 5, and checking to see if the result is a multiple of 8. I eventually get to 96 (= 13.7+5, so p=7), and 96 = 8.12 of course. Hence 8x=96(mod13) from which it follows that x=12(mod13). Checking the correctness of this is straightforward by the inverse process 8.12(mod13)=96(mod13)=5(mod13).

Seems like you just developed the algorithm right there. I wish I could explain this inperson - it is hard to write, but easy for a computer to understand.

Also, p can't be larger than n by defintion, so your algorithm is not that mundane or tedious unless you are solving by hand with an enormous modulo.

 

[PatsFan34]

I'm so glad the Yankees are losing right now!

 

[chesty]

Wait till I start my masters this fall then ask me.

 

[hinson4]

The question as I understand it is that If 8x = 5(mod13)........... then the answer is 12

so
8 *12 = 96
96 mod 13 = 5

this makes the question (8 * x ) mod 13 = 5, then what is x?
or (A * X) mod B = C

If you are trying to program this then there are a number of solutions..... I provided an answer in Java

class testing
{
public static void main(String[] args)
{
//(8 * x) mod 13 = 5
// this means that x is divisible by 8
int A, B, C, x;
//change values here
A = 4;
B = 99;
C = 6;
for(x = 1; ((A * x) % B) != C; x++)
{
System.out.println("Now testing the number = " + x);
}

System.out.println("The answer (x) = " + x);
}
}


the answer in this case is 51

-Hinson

 

[nevertoobig]

Thanks for all of your help. I don't have a clue as to whether or not these are what my friend was looking for because I don't understand this stuff myself.

Thanks again for the replies, I'm sure some of it will come in helpful.