please show all the steps Prove every m epsilon N has a base

please show all the steps

Prove: every m epsilon N has a base-n representation, where n greaterthanorequalto 2. Prove: (for all m, n epsilon N) (there Exist x, y epsilon Z) gcd(m, n) = mx: + ny.

Solution

Suppose that m and n are relatively prime. Then gcd(m; n) = 1 and so by Theorem 3.13,
there exists x; y 2 Z such that 1 = mx + ny.
Conversely, suppose that there exists m; n 2 Z such that mx + ny = 1. Just suppose that
gcd(m; n) = d > 1. Choose a positive, prime number p such that pjd. Then pjm and pjn so there
exists k; l belongs to Z such that m = kp and n = lp. Then 1 = mx + ny = kpx + lpy = p(kx + ly), and
so pj1. This is a contradiction because if p/1, then p <=1, but by de nition, p > 1 because p is a
positive, prime number. Therefore, it must be that gcd(m; n) = 1 and so gcd(m; n) = 1.