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?

  • 2
    $\begingroup$ Hint: If $p$ is prime, and $p|xy$, then $p|x$, or $p|y$. $\endgroup$ – quasi May 16 '18 at 3:26
  • $\begingroup$ 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/… $\endgroup$ – Mr Pie May 16 '18 at 4:07
  • $\begingroup$ @quasi I got it. Thnx. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.