# Thread: Modulo/congruence proof help

1. ## Modulo/congruence proof help

1. If $(a,n) = 1,$ then $\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 $x,y \in \mathbb{Z}$ such that: $(a,n) = 1 \ \Leftrightarrow \ ax + ny = 1$

You can also show that this $b$ is unique. by supposing that there exists more than one unique solution, i.e. $ar \equiv 1 \ (\text{mod } n)$ and $as \equiv 1 \ (\text{mod } n)$ for some $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 $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 $ny=1-ax$ but I need $a-b=nq$ or $b-a=nq$ right? I could divide by x, giving $\frac {ny}{x}=\frac {1} {x} -a$ but can I let $b=\frac {1} {x}$ since that's a fraction?

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

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

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

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