Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

vkditya0997's blog

By vkditya0997, history, 4 years ago, In English,

Hello Codeforces,

I was trying this 603B - Moodular Arithmetic, I couldn't get the idea and read the editorial.

I have a doubt.


for k >  = 2 case :

we choose m such that k m = 1 mod p

and also it has been proved that f(k i * n mod p ) = k i * f(n) mod p

and now if we choose some f(n) , we get the value of f(n) , f(k * n mod p ) ,.... f(k m - 1 * n mod p )

Understood until this point


I didn't understand from here..

Therefore, if we choose f(n) of p - 1 / m integers n, we can get value of all p-1 non-zero integers. Since f(n) can be chosen in p ways for each of the p - 1 / m integers, the answer is p p - 1 / m

Can someone please help in understanding this one?

Thanks in Advance!

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

p prime implies there exists g (generator) such that {g i: 1 ≤ i ≤ p - 1} = {1, ..., p - 1}. g will have order p - 1. So g n = k where n = (p - 1) / m since g p - 1 = g nm = k m = 1.

Consider the sets G i = {g i, kg i, ..., k m - 1 g i} for all 1 ≤ i ≤ n. Every element from 1 to p - 1 appears in exactly one of the G i (cosets).

Consider any G i and . Assigning f(x) a value defines f on all other elements in G i. So to fully define f we only need to assign one value from each G i. So p choices for each of the n sets or p (p - 1) / m choices overall.