Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

my e=131 and p=18181

to find by d I must solve the linear diophantine equation 131*d=1 mod 18180 LDE to solve: 131d+18180y=1

after solving this I get d=-1249 and y=9 the problem is if I take my cipher text C which is say 9805 and try to decipher it with d=-1249 i get a massive error because d has to be positive to use it for deciphering. How can I find a d or make this d positive so I can use it for deciphering?

I think I got the answer, I need to write my solution for d,y in the form which gives all solutions and plug in a number and find a positive d that works

share|cite|improve this question
Dear Raynos, we do not delete questions which have answers (and much less upvoted anbd accepted answers!) unless there is a very good reason. – Mariano Suárez-Alvarez Feb 27 '12 at 8:28
up vote 1 down vote accepted

Let $(x_0,y_0)$ be a particular solution of the linear Diophantine equation $$131x+ 18180y=1.$$ Then all integer solutions are given by $$x=x_0+18180t,\qquad y=y_0-131t,$$ where $t$ ranges over the integers.

In your problem, the variable I called $x$ is called $d$. You want the "multiplier" of $d$ to be positive. Take, for example, $t=1$.

Remark: In general, suppose that you have found a solution in $(x_0,y_0)$ in integers, not necessarily positive, of the equation $ax+by=k$. Let $d$ be the greatest common divisor of $a$ and $b$, and let $a=da'$, $b=db'$. Then all integer solutions of $ax+by=k$ are given by $x=x_0+b't$, $y=y_0-a't$, where $t$ ranges over the integers. Thus if you have found one solution, all the solutions are fairly straightforward to describe.

share|cite|improve this answer

Remember that you are not solving an equation but a congruence, so when you write the answer $d=-1249$ what you really meant to write was $d\equiv -1249\pmod{18180}$. Do you know how to get a positive $d$ satisfying that congruence?

share|cite|improve this answer
yes for this case an easy solution is to do 18180-1249 to get my d – Raynos Feb 27 '12 at 6:43

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.