For a prime $p$ and any integer $a$, $\gcd(p,a)$ is $p$ when $p \mid a$ and $1$ otherwise; so $p \nmid a$ makes $p$ and $a$ coprime

Given: A prime $p$, an integer $a$, and $g := \gcd(p,a)$ (Common divisor, and the greatest common divisor $\gcd(a,b)$, with the convention $\gcd(0,0) := 0$).

$p > 1$, and every positive divisor $d$ of $p$ satisfies $d = 1$ or $d = p$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$).

$g \ge 0$, $g \mid p$, $g \mid a$, and every common divisor of $p$ and $a$ divides $g$ (Every common divisor of $a$ and $b$ divides $\gcd(a,b)$; consequently $d = \gcd(a,b)$ exactly when $d \ge 0$, $d \mid a$, $d \mid b$, and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a,b) = (0,0)$ as well, Common divisor, and the greatest common divisor $\gcd(a,b)$, with the convention $\gcd(0,0) := 0$).

$\gcd(u,v) \ge 1$ unless $u = v = 0$, in which case $\gcd(u,v) = 0$ ($\gcd$ is symmetric and unchanged by signs: $\gcd(a,b) = \gcd(b,a) = \gcd(|a|,|b|)$; moreover $\gcd(a,0) = |a|$, $\gcd(a,1) = 1$, $\gcd(a,a) = |a|$, and $\gcd(a,b) \ge 1$ unless $a = b = 0$).

Divisibility is reflexive and transitive: $u \mid u$ for every $u$, and $d \mid u$ with $u \mid v$ gives $d \mid v$ (Divisibility is reflexive and transitive on $\mathbb{Z}$, and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$; also $d \mid a$ implies $d \mid ac$, $-d \mid a$ and $d \mid -a$, Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$).

$u \mid 1$ exactly when $u = 1$ or $u = -1$ ($(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$).

$u$ and $v$ are coprime exactly when $\gcd(u,v) = 1$ (Coprime integers: $\gcd(a,b) = 1$).

The order on $\mathbb{Z}$ is total, antisymmetric and transitive and is compatible with addition; $x < y$ means $x \le y$ together with $x \ne y$ (The integers form a totally ordered ring, Order on the integers).

The embedding $\iota : \mathbb{N} \to \mathbb{Z}$ is injective, preserves the order, and has as image exactly the nonnegative integers, with $\iota(0) = 0$ and $\iota(1) = 1$; and $0 \ne 1$ in $\mathbb{N}$ (The naturals embed in the integers, The natural numbers $\mathbb{N}$ (von Neumann), The integers as equivalence classes of pairs of naturals).

$\mathbb{Z}$ is a commutative ring: addition is associative and commutative, $x + 0 = x$, and every $x$ has an additive inverse $-x$, with $-(-x) = x$; we write $u - v$ for $u + (-v)$ (The integers form a commutative ring, Arithmetic on the integers).