# modular cipher d is negative how do I make it positive?

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

-
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

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.
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?