1. ## Modulo/congruence proof help

1. If $\displaystyle (a,n) = 1,$ then $\displaystyle \exists b \in Z s.t. ab\equiv1 (mod n).$

2. Every positive integer is congruent to the sum of its digits (mod 9).

2. 1. Use the fact that there exists $\displaystyle x,y \in \mathbb{Z}$ such that: $\displaystyle (a,n) = 1 \ \Leftrightarrow \ ax + ny = 1$

You can also show that this $\displaystyle b$ is unique. by supposing that there exists more than one unique solution, i.e. $\displaystyle ar \equiv 1 \ (\text{mod } n)$ and $\displaystyle as \equiv 1 \ (\text{mod } n)$ for some $\displaystyle r,s \in \mathbb{Z}$ and arriving at a contradiction.

2. Here: Congruence

3. Thanks for the link for the second one! We just had to prove that $\displaystyle 10^n \equiv 1 (mod 9)$ so I guess I should have been able to figure that one out but I needed a push in the right direction!

For the first one, I'm still unsure. I actually had what you have written on my paper, but I'm still unsure of how the "b" fits into the problem. I have $\displaystyle ny=1-ax$ but I need $\displaystyle a-b=nq$ or $\displaystyle b-a=nq$ right? I could divide by x, giving $\displaystyle \frac {ny}{x}=\frac {1} {x} -a$ but can I let $\displaystyle b=\frac {1} {x}$ since that's a fraction?

4. We know that there exists some $\displaystyle x,y \in \mathbb{Z}$ such that: $\displaystyle (a,n) = 1 \ \Leftrightarrow \ ax + ny = 1 \ \Leftrightarrow ax = 1 + (-y)n$

By definition, this is the same as saying: $\displaystyle ax \equiv 1 \ (\text{mod } n)$

But since $\displaystyle x$ has already been determined, this is the $\displaystyle b$ we were looking for !

5. Oh, duh! Haha for some reason I was thinking I needed to prove $\displaystyle a\equiv b (mod n)$. Thanks for all of your help!