Multiplicative order: Difference between revisions
Content added Content deleted
(page creation) |
(make this a task) |
||
Line 1: | Line 1: | ||
{{task}} |
|||
The <i>multiplicative order</i> of<tt> x </tt>relative to<tt> y </tt>is |
The <i>multiplicative order</i> of<tt> x </tt>relative to<tt> y </tt>is |
||
the least integer<tt> n </tt>such that<tt> x^n </tt>is<tt> 1 </tt>modulo<tt> y</tt> . |
the least integer<tt> n </tt>such that<tt> x^n </tt>is<tt> 1 </tt>modulo<tt> y</tt> . |
Revision as of 00:56, 8 December 2007
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
The multiplicative order of x relative to y is the least integer n such that x^n is 1 modulo y . For example, 37 mo 1000 is 100 because 37^100 is 1 modulo 1000 (and no number smaller than 100 would do).
Note that the multiplicative order is undefined if x and y are not relatively prime.
J
mo=: 4 : 0 a=. x: x m=. x: y assert. 1=a+.m *./ a mopk"1 |: __ q: m ) mopk=: 4 : 0 a=. x: x 'p k'=. x: y pm=. (p^k)&|@^ t=. (p-1)*p^k-1 NB. totient 'q e'=. __ q: t x=. a pm t%q^e d=. (1<x)+x (pm i. 1:)&> (e-1) */\@$&.> q */q^d )
For example:
37 mo 1000 100 2 mo _1+10^80x 190174169488577769580266953193403101748804183400400