modular multiplication

Tony

2014-10-26 4:42 am

(12x)mod147 = 7
is there any x in Z147(0,1,....,146) to satisfy the equation?

as far as I learned, If 12 has the multiplicative inverse in Z147,
x = (12^(-1) * 7)mod147
and gcd(12,147)=1, 12 has the multiplicative inverse in Z147 and it is Amod147,
where 12A+147B=1.
combine these two statements,
gcd(12,147)=1, x = (12^(-1) * 7)mod147

however, gcd(12,147)=3≠1, it implies that there exist some b in Z147,
(12x)mod147 ≠ b,
but I don't know whether b is 7 or not?

so, how do I deal with this kind of problem?

回答 (1)

邊位都好

2014-10-26 5:06 pm

✔ 最佳答案

You can think it in this way :As (12x) mod 147≡7 and (147x) mod 147≡0, you can re-write in this way,12x≡7 ⋯⋯⋯⋯⋯ (i)==> 144x≡84 ⋯⋯ (ii)147x≡0 ⋯⋯⋯⋯ (iii)(iii) - (ii), gets3x = -84==> 12x≡-336≡42Contradict with (i), so, no such x exist.

2014-10-26 09:37:20 補充：
Sorry, the last second written wrongly, it should be,

==> 12x≡-336≡-42≡105

👍 0 👎 0