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.

Given $c$ and $n$ in $c = 6a\mod n$, how can I find the lowest positive integer value for $a$?

I could find it iteratively by rewriting as $\displaystyle a = \frac{c + xn}{6}$ and increasing $x$ until $a$ is an integer, but I would prefer a more efficient solution. Is there another way to do this?

Edit: Combined two variables.

Here is an example: $3 = 6a\mod 11$

share|improve this question
1  
If $\gcd(n,6)=1$ then you actually calculate $\frac{b-c}{6}\pmod n$, and the result is $a$. –  Asaf Karagila Jun 11 '11 at 19:37
1  
The Euclidean Algorithm is a pretty standard way to do this. –  Ryan Budney Jun 11 '11 at 19:43
    
And if it's not then your equation might have no solutions at all (e.g. $n = 6$ removes $a$ from the equation altogether). –  Marek Jun 11 '11 at 19:43
    
@jnm2: Do you also know $\gcd(n,6)$? –  Asaf Karagila Jun 11 '11 at 19:45
    
Yes, $n$ will be a prime 5 or greater. But$ \frac{b-c}{6}$ gave me a fractional result. I'm looking for an integer. –  jnm2 Jun 11 '11 at 19:47
show 2 more comments

2 Answers

up vote 10 down vote accepted

First, general comments.

The congruence $$Ax\equiv c \pmod{n}$$ has a solution $x$ if and only if $\gcd(A,n)|c$. If it does, the standard method is to use the extended Euclidean algorithm to find integers $r$ and $s$ such that $$d = Ar + ns$$ (where $d=\gcd(A,n)$); then multiply by $\frac{c}{d}$ (an integer, since $d|c$) to get $$c = A\left(\frac{rc}{d}\right) + n\left(\frac{sc}{d}\right).$$ So one solution is $a=\frac{rc}{d}$. Finding the remainder of $\frac{rc}{d}$ modulo $n$ can be done by direct division. If $d\gt 1$, then you still need to make sure that there is no smaller division by comparing with $\frac{n}{d}$, since given any particular solution to $Ax\equiv c\pmod{n}$, then $x\pm\frac{n}{d}$ is also a solution.

The extended Euclidean algorithm is pretty efficient, but even so there are a few tweaks that can be done to make it even more so (e.g., instead of always requiring the remainder to be positive, you can require that the remainder lie between $-\frac{n}{2}$ and $\frac{n}{2}$). The other steps are pretty efficient as well.


Added. If, as you indicate in comments, the modulus is prime, you can also use Gauss's method. Write the fraction you want (in this case, $\frac{c}{A}$), and multiply numerator and denominator by the smallest $k$ such that $Ak\gt n$ (or such that $Ak$ has a small remainder in absolute value modulo $n$); then reduce and repeat until you get to a denominator equal to $1$.


Now, your particular issue.

However, the case of $A=6$ and prime modulus is particularly simple, since every prime other than $3$ is either congruent to $1$ or to $-1$ modulo $6$. So write $n=6k\pm 1$, and use $k$: For the example you write, note that $11 = 2\times 6 - 1$: $$a\equiv \frac{3}{6} = \frac{2\times 3}{2\times 6} = \frac{6}{12} \equiv \frac{6}{1} \equiv 6\pmod{11}.$$ For another, say you want to solve $$7\equiv 6a\pmod{43}.$$ Since $43 = 6\times 7 + 1$, then we have $$a \equiv \frac{7}{6} =\frac{7\times 7}{7\times 6} \equiv \frac{49}{42}\equiv \frac{6}{-1}= -6 \equiv 37\pmod{43}.$$ Etc.

In summary. For a prime modulus $n\gt 3$, divide $n$ by $6$, and write $n=6k\pm 1$. If $n=6k-1$, then $a\equiv ck\pmod{n}$, so then you just need to divide $ck$ by $n$ to get the remainder. If $n=6k+1$, then $a\equiv -ck$, so find the remainder for $-ck$ instead.

share|improve this answer
    
Thank you, very helpful. –  jnm2 Jun 11 '11 at 23:42
add comment

HINT $\:$ If it is solvable then you can cancel $\rm\:gcd(6,n)\:,\:$ yielding $\rm\: d\:a\ = b\ (mod\ m)\:$ for $\rm\:d\:$ dividing $6\:.\:$ Now simply multiply through by $\rm\:1/d\ (mod\ m)\:,\:$ which is easily directly computable, namely

$\rm\displaystyle\qquad\qquad\quad\: m\:\equiv\: \pm 1\ \ (mod\ d)\ \ \Rightarrow\ \ \frac{1}d\:\equiv\: \frac{1\mp m}{d}\ \ (mod\ m)\:.\ $

E.g. $\rm\displaystyle\qquad\ {\color{red}{25}}\:\equiv\: {\color{red}+1}\ \ (mod\ 6)\ \ \Rightarrow\ \ \frac{1}6\:\equiv\:\frac{1{\color{red}{-25}}}6\:\equiv -4\ \ (mod\ 25)$

E.g. $\rm\displaystyle\quad\ \ \ \ {\color{red}{23}}\:\equiv {\color{red}{-}}1\ \ (mod\ 6)\ \ \Rightarrow\ \ \frac{1}6\:\equiv\:\frac{1{\color{red}{+23}}}6\:\equiv\ \ 4\ \ \ (mod\ 23)$

Note that the reason this works out so simply is due to the fact that the only numbers coprime to $6$ are those $\rm\:\equiv \pm 1\ (mod\ 6)\:.$

share|improve this answer
add comment

Your Answer

 
discard

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.