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