0
$\begingroup$

How do I begin to prove that for every positive integer $q$, $q$ can be written in the form $q = y^2z$ for some integers $y$ and $z$ where $z$ is a possibly empty product of distinct primes?

The part that really stumps me is where $z$ is a possibly empty product of distinct primes. Any help to get me on the correct path would be appreciated.

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ Possible duplicate of math.stackexchange.com/questions/21282/… $\endgroup$ – lhf Mar 30 '17 at 12:24
  • $\begingroup$ Why do you want to prove that by induction? That makes thing a lot more elaborate, but basically the way you elide induction is by handwaving... $\endgroup$ – skyking Mar 30 '17 at 12:28
  • $\begingroup$ Hrm, I guess it doesn't have to be an inductive proof, I just assumed it must be. $\endgroup$ – user430779 Mar 30 '17 at 14:47
1
$\begingroup$

Let $q =p_1^{r_1} \cdots p_n^{r_n}$ (By fundamental thm of arithmetics), where $p_i$ prime, $r_i \geq 0$, then wlog, let $r_i =2s_i +t_i$, where $t_i =0, 1$ and $s_i \geq 0$. Then, $y =p_1^{s_1} \cdots p_n^{s_n}$ and $z =p_1^{t_1} \cdots p_n^{t_n}$, yields $q =y^2 z$.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Sorry, do you require the proof to be inductive?? $\endgroup$ – Violapterin Mar 30 '17 at 12:28
0
$\begingroup$

To do it inductively what you can do is to use a generalized form of the induction principle:

Suppose that $P(x_1)$ is true and that for all $n$ that $(\forall j< n: P(x_j)) \Rightarrow P(x_n)$, then $P(x_n)$ is true for all $n>0$.

The difference here is that we instead of using the immediately previous number in the induction step allow us to use all previous ones(*).

Obviously the statement is true for $1$.

Now suppose it's true for all numbers below $q$. As we've seen that it's true for $q=1$ already we can assume that $q>1$. Then we can find a prime that divides $q$(**), so we can write $q = \tilde q p$ and we know that $\tilde q = \tilde y^2 \tilde z$ where is a product of distinct primes. Now $p$ is either one of those primes or it isn't. If it isn't we have that $\tilde zp$ is a product of distinct primes, that is $q = \tilde q p = \tilde y^2 (\tilde zp)$. Otherwise we have that $\tilde z/p$ is a product of distinct primes(***). So we have $q = (\tilde q p)^2 (\tilde z/p)$. So we have shown that it follows that it's true for $q$.

Now by induction it's true for all $q$.


(*) Can be proven by induction too: What you use is to reformulate the induction step statement (using that $\psi \Rightarrow \phi$ implies that $\psi \Rightarrow \psi\land\phi$) as $(\forall j<n: P(x_j)) \Rightarrow (\forall j<n+1: P(x_j))$. Now you have a classic induction step and it follows that for all $n>1$ that $\forall j<n+1: P(x_j)$ and therefore especially that $P(x_n)$.

(**) Can be proven by induction too with the same extended induction principle (with the twist that we start at $2$ instead of $1$): It's obviusly true for $2$. Now if it's true for all less than $q$ we have that since $q$ is composite that $q=ab$ where $b<q$ which in turn means that $b = cp$ for some prime $p$ so $q = (ac)p$ for some prime $p$. By extended induction it follows that all $q>1$ can be written $q=rp$ for some prime $p$.

(***) I guess that can be proven by induction too:)

| cite | improve this answer | | | | |
$\endgroup$

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.