# Thread: modular equations

1. ## modular equations

1. Let $n$ and $a$ be positive integers and let $d = \gcd(a,n)$. Show that the equation $ax = 1\ \text{mod} \ n$ has a solution if and only if $d = 1$.

Proof. $(\Rightarrow)$ Suppose $ax = 1\ \text{mod} \ n$ has a solution. Then $ax-1 = nk$ for some $k \in \mathbb{Z}$. So $x = (nk+1)/a$. From here it follows that $a$ and $n$ are coprime? $(\Leftarrow)$ Suppose $d=1$. Then $a$ and $n$ are coprime. So $ax = 0\ \text{mod} \ n$ has no solutions. Hence $ax = 1\ \text{mod} \ n$ has a solution. $\square$

2. Let $n$ be a fixed positive integer greater than $1$. For any integers $i$ and $j$, prove that $i \ \text{mod} \ n + j \ \text{mod} \ n = (i+j) \ \text{mod} \ n$.

Proof. So $i = nq+r$ and $j = nq'+r'$ where $r \leq q$ and $r' \leq q'$. Then $i+j = n(q+q') + (r+r')$. $\square$

Are these somewhat correct?

2. Originally Posted by Sampras
1. Let $n$ and $a$ be positive integers and let $d = \gcd(a,n)$. Show that the equation $ax = 1\ \text{mod} \ n$ has a solution if and only if $d = 1$.

Proof. $(\Rightarrow)$ Suppose $ax = 1\ \text{mod} \ n$ has a solution. Then $ax-1 = nk$ for some $k \in \mathbb{Z}$. So $x = (nk+1)/a$. From here it follows that $a$ and $n$ are coprime? $(\Leftarrow)$ Suppose $d=1$. Then $a$ and $n$ are coprime. So $ax = 0\ \text{mod} \ n$ has no solutions. Hence $ax = 1\ \text{mod} \ n$ has a solution. $\square$

2. Let $n$ be a fixed positive integer greater than $1$. For any integers $i$ and $j$, prove that $i \ \text{mod} \ n + j \ \text{mod} \ n = (i+j) \ \text{mod} \ n$.

Proof. So $i = nq+r$ and $j = nq'+r'$ where $r \leq q$ and $r' \leq q'$. Then $i+j = n(q+q') + (r+r')$. $\square$

Are these somewhat correct?
Up to here is awsome

$(\Rightarrow)$ Suppose $ax = 1\ \text{mod} \ n$ has a solution. Then $ax-1 = nk$ for some $k \in \mathbb{Z}$.
but from here we can't really divide by a in $\mathbb{Z}$

but we do have $ax-1 = nk \iff ax+(-k)n=1$ this tells us that gcd(a,n)=1 becuase we have expressed 1 as a linear combination of a and n.

$(\Leftarrow)$ Suppose $d=1$. Then $a$ and $n$ are coprime. So $ax = 0\ \text{mod} \ n$ has no solutions. Hence $ax = 1\ \text{mod} \ n$ has a solution. $\square$
ummm not quite first x=0 is a solution

Then by the Euclidean algorithm there exists $\alpha,\beta \in \mathbb{Z}$ such that $\alpha a +\beta n =1$

use this to show that there does exists a solution.

3. Originally Posted by Sampras
1. Let $n$ and $a$ be positive integers and let $d = \gcd(a,n)$. Show that the equation $ax = 1\ \text{mod} \ n$ has a solution if and only if $d = 1$.

Proof. $(\Rightarrow)$ Suppose $ax = 1\ \text{mod} \ n$ has a solution. Then $ax-1 = nk$ for some $k \in \mathbb{Z}$. So $x = (nk+1)/a$. From here it follows that $a$ and $n$ are coprime? $(\Leftarrow)$ Suppose $d=1$. Then $a$ and $n$ are coprime. So $ax = 0\ \text{mod} \ n$ has no solutions. Hence $ax = 1\ \text{mod} \ n$ has a solution. $\square$
Use the fact that $\gcd(a,n)=1$ if and only if there exist integers $r,s$ with $ra+sn=1.$ Thus

$ax\equiv1\,(\bmod\,n)$ has solution in $x$

$\iff\ ax+kn\,=\,1$ for some integer $k$

$\iff\ \gcd(a,n)\,=\,1$

Originally Posted by Sampras
2. Let $n$ be a fixed positive integer greater than $1$. For any integers $i$ and $j$, prove that $i \ \text{mod} \ n + j \ \text{mod} \ n = (i+j) \ \text{mod} \ n$.

Proof. So $i = nq+r$ and $j = nq'+r'$ where $r \leq q$ and $r' \leq q'$. Then $i+j = n(q+q') + (r+r')$. $\square$

Are these somewhat correct?
What you want to prove is that if $r\equiv i\,(\bmod\,n)$ and $r'\equiv j\,(\bmod\,n)$ then $r+r'\equiv i+j\,(\bmod\,n).$ Your proof is essentially correct, but it might be better to write the $r$ and $r'$ on the left-hand side instead. (NB: There is no need to assume $r\le q$ or $r'\le q'.)$

4. Originally Posted by TheAbstractionist
Use the fact that $\gcd(a,n)=1$ if and only if there exist integers $r,s$ with $ra+sn=1.$ Thus
$ax\equiv1\,(\bmod\,n)$ has solution in $x$
$\iff\ ax+kn\,=\,1$ for some integer $k$

$\iff\ \gcd(a,n)\,=\,1$

What you want to prove is that if $r\equiv i\,(\bmod\,n)$ and $r'\equiv j\,(\bmod\,n)$ then $r+r'\equiv i+j\,(\bmod\,n).$ Your proof is essentially correct, but it might be better to write the $r$ and $r'$ on the left-hand side instead. (NB: There is no need to assume $r\le q$ or $r'\le q'.)$
That's only for Euclidean algorithm?

5. Originally Posted by Sampras
That's only for Euclidean algorithm?
There is no need to use the Euclidean algorithm for this problem.

6. Originally Posted by TheAbstractionist
There is no need to use the Euclidean algorithm for this problem.
But you assume $r \leq q$ and $r' \leq q'$ only if you were to use the Euclidean algorithm?

7. No, $r, r' < n$, but it doesn't really matter for this proof.