# Thread: modular equations

1. ## modular equations

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

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

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

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

Are these somewhat correct?

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

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

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

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

Are these somewhat correct?
Up to here is awsome

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

but we do have $\displaystyle 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.

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

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

use this to show that there does exists a solution.

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

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

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

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

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

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

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

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

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

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

What you want to prove is that if $\displaystyle r\equiv i\,(\bmod\,n)$ and $\displaystyle r'\equiv j\,(\bmod\,n)$ then $\displaystyle r+r'\equiv i+j\,(\bmod\,n).$ Your proof is essentially correct, but it might be better to write the $\displaystyle r$ and $\displaystyle r'$ on the left-hand side instead. (NB: There is no need to assume $\displaystyle r\le q$ or $\displaystyle 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 $\displaystyle r \leq q$ and $\displaystyle r' \leq q'$ only if you were to use the Euclidean algorithm?

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