$p * z - q * n = 1 \implies \gcd{(z,n)} = 1$

Question

Prove that:

let n $\in \mathbb{N} $ and $ z \leq n \in \mathbb{Z}$

$\exists p,q \in \mathbb{Z}: p * z - q * n = 1 \implies \gcd{(z,n)} = 1$

You forgot the dollars in the heading...also use $\gcd$ to get $\operatorname{gcd}(z,n)$ — Anindya Prithvi, Nov 22 '20 at 18:37
Actually Bezout's theorem is a consequence of this. But note $\gcd(n,z)|n$ and $\gcd(n,z)|z$ so $\gcd(n,z)$ will divide any $pn + qz$. SO if any $pn + qz = 1$ then $\gcd(n,z)|1$. — fleablood, Nov 22 '20 at 18:39

score 3 · Accepted Answer · answered Nov 22 '20 at 18:37

3

Note that $\gcd(n,z)|n$ and $\gcd(n,z)|z$ so $\gcd(n,z)| pz - qn$ for all $p,q\in \mathbb Z$.

SO if there is any $p,q \in \mathbb Z$ so that $pn-qz = 1$ then $\gcd(n,z)|1$.

answered Nov 22 '20 at 18:37

fleablood

score 2 · Answer 2 · answered Nov 22 '20 at 18:37

2

Let $ c$ be a common divisor of $ z $ and $ n $.

$$c|z \wedge c|n \implies $$

$$c|pz \wedge c|qn \implies$$

$$c|(pz-qn) \implies $$ $$c|1 \implies $$ $$|c|=1 \implies$$ $$gcd(z,n)=1$$

answered Nov 22 '20 at 18:37

hamam_Abdallah

2 Answers2