Task 144 Explanation

Back to Problem Solutions forum

OldProgrammer     2015-05-31 01:18:13

The explanation says, "But this means that a=inv(A) - great! Of course if a happens to be negative we should "wrap" it around the lower bound of the field, i.e. subtract it from M.". That looks incorrect to me e.g. -10 mod 3 = 2, whereas 3 - -10 (= 13) mod 3 = 1. M should repeatedly be added to a until
the sum becomes positive.

n = bq + r => n mod q = r q - n = bq + (q - r) => q - n mod q = q - r

I wasted a bit of time on the task using the subtraction so, I think, that the text needs fixing.

Rodion (admin)     2015-06-08 05:51:48
User avatar

Thanks a lot for your suggestion!

> That looks incorrect to me e.g. -10 mod 3 = 2, whereas 3 - -10 (= 13) mod 3 = 1. M should repeatedly be added to a until the sum becomes positive.

Yes, now it looks incorrect to me too. I will try to change the explanation right now!

OldProgrammer     2015-06-08 21:50:03

Thanks for looking into this.

Please login and solve 5 problems to be able to post at forum