# Proof of $\exists \; k \in \mathbb{Z}$ such that $q \mid (b^k)$ theorem

I learnt recently that:

For $b, q \in \mathbb{Z}$:

$\exists \; k \in \mathbb{Z}$ such that $q \mid (b^k) \implies$ all prime factors of $q$ are also prime factors of $b$

I couldn't find a proof of this theorem online (maybe because I don't know what this theorem is called).

Can somebody provide me with a simple proof of this fact?

• Hint: If $p$ is prime, and $p|xy$, then $p|x$, or $p|y$. – quasi May 16 '18 at 3:26
• Adding tp what @quasi said, that is known as Euclid's Lemma. Below is a link to perhaps a useful post: math.stackexchange.com/questions/2780075/… – Mr Pie May 16 '18 at 4:07
• @quasi I got it. Thnx. – Truth-seek May 16 '18 at 10:45

If $q\mid b^k$ .then,all prime factors of $p$ is also prime factors of $b$. we prove this theorem by using contradiction.

we consider that,If $q\mid b^k$ .then,some prime factors of $p$ is prime factors of $b$.

let $b=b_1. b_2.b_3...b_n$

and $q=q_1. q_2.q_3...q_n$ let $q_n$ be one of the prime factors of$p$ but, it is not a prime factor of $q$

$q\mid b^k\implies b^k=q x$ where $x$ is an integer.

$({b_1. b_2.b_3...b_n})^k=x.q_1. q_2.q_3...q_n$

RHS is a multiple of $q_1$.but,LHS is not a multiple of $q_1$ . because $q_1$ is not a prime factor of $q$ . by contradiction this equality does not occurs.

so,If $q\mid b^k$ .then,all prime factors of $p$ is also prime factors of $b$.