# Thread: Cryptography - Modular Arithmetic

1. ## Cryptography - Modular Arithmetic

This is my first post.

I'm having a bit of trouble getting started with some questions in a text I am going though. Most of the questions are similar,so if I can get through one of them, I'm assuming it would serve as a guide to getting through the rest. Here are a few of the presented questions:

• Let a ∈ Zn. Show that a and n are relatively prime if and only if there exists an element b ∈ Zn such that ab=1.

I realize that to show that numbers are relatively prime, I have to show that gcd(a,n)=1 -- I guess using Euclidean Algorithm, which I know how to do with actual numbers.
• Let a ∈ Zn. Show that a and n are relatively prime if and only if a's row in the multiplication table of Zn contains every element of Zn.

???
• Show that n is a prime number if and only if in the multiplication table for Zn, except for the first row, all elements of Zn appear in each row.

I understand what the problem is asking, but I have no idea how to begin proving it.
If someone can shed some light or provide some guidance, it is greatly appreciated!

2. For the first question, suppose that $\displaystyle ab \equiv 1 \mod n$ for some integer b but a and n are not relatively prime. Then $\displaystyle ak \equiv 0 \mod n$ for some integer k such that $\displaystyle 0 < k < n$. By the first equation, $\displaystyle abk \equiv k \mod n$, but since $\displaystyle ak \equiv 0 \mod n$, $\displaystyle abk \equiv 0 \mod n$, which is a contradiction.

Conversely, suppose that $\displaystyle \gcd(a, n) = 1$. Then there exist integers p, q such that $\displaystyle pa + qn = 1$. Hence $\displaystyle pa = 1 - qn$ and $\displaystyle pa \equiv 1 \mod n$. This also means that $\displaystyle (p + kn)a \equiv 1 \mod n$, and $\displaystyle p + kn \in \mathbb{Z}_n$ for some integer k.