bagdat.zhursynbek.ru's blog

Please help on mathematical problem :)
By bagdat.zhursynbek.ru, history, 7 years ago, In English

Hello Codeforces.

Please help on this problem. Explain how to solve.

Given:
A = (B * C + D) mod E.

Find B.
B = ????
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it 
A = B * C + D (mod E)
A - D = B * C (mod E)
B = (A - D) * C^(-1) (mod E)
C^(-1) = C^(φ(E) - 1) (mod E), where φ(n) is Euler''s phi function
If E is prime number then φ(E) = E - 1
Answer:
B = (A - D) * C^(φ(E) - 1) (mod E)
(mod E) means that all operations are calculated modulo E
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    C^(-1) = C^(φ(E) — 1) (mod E) is only valid when C and E are coprime.

    → Reply