Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

On a practice final exam (for a Computer Security course), I am given the following equation to solve, but I have no idea how to solve it: $$324x \bmod 121 = 1.$$

Any direction?

share|improve this question

2 Answers 2

HINT $\ $ One can easily solve it mod $11$ then lift the solution to one mod $11^2$

$\rm\ \ mod\ 11:\ \ \ \ x = 1/(324) = 1/(-6) = -2\ \ $ so $\rm\ x = -2 + 11\ n$

$\rm\ \ mod\ 121:\ \ \: 1 = 324\ x = (-6 + 11\cdot 30)\ (-2 + 11\ n)\ \ =\ 55\ n - 43\ \ \Rightarrow\ \ 55\ n = 44$

Dividing by $11$ we deduce $\rm\ 5\ n = 4\ \:(mod\ 11)\ $ so $\rm\ n =\ \ldots\ \: $ The method generalizes, e.g.

$\rm\quad\quad a\ x\ =\ 1 + b\ m\ \ \Rightarrow\ \ a\ x\ (2-a\ x)\ =\ (1 + b\ m)\ (1-b\ m) = 1 - (b\ m)^2\equiv 1\:\ (mod\ m^2) $

so $\rm\ a^{-1}\equiv x\:\ (mod\ m)\ $ lifts to $\rm\ a^{-1}\equiv x\ (2-a\ x)\ \ (mod\ m^2)\:.\:$ This method of lifting solutions is a special case of a very powerful generalization of Newton's method known as Hensel's Lemma.

share|improve this answer

You need the Extended Euclidean Algorithm which solves the problem of finding modular inverses. Bezout's identity guarantees that there is a solution.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.