- #1

Math100

- 773

- 219

- Homework Statement
- Let ## S=\{1, 5, 9, 13, 17,...\} ## be the set of positive integers of the form ## 4k+1 ##. An element ## p ## of ## S ## is an S-prime if ## p>1 ## and the only elements of ## S ## that divide ## p ## are ## 1 ## and ## p ##. (For example, ## 9 ## and ## 49 ## are S-primes.) An element of ## S ## that is not ## 1 ## or an S-prime is an S-composite. (For example, ## 25=5\cdot 5 ## is an S-composite.)

Use strong induction to prove that every S-composite can be expressed as a product of S-primes.

- Relevant Equations
- None.

The proof is by strong induction.

Suppose ## p ## is an S-prime.

Then ## p=4k+1 ## for some ## k\in\mathbb{N} ##.

Let ## n ## be an S-composite such that ## n=p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{r}^{k_{r}} ## where ## p_{i} ## are all S-primes.

(1) When ## k=1 ##, the statement is ## p=4(1)+1=5 ##, which is true, because ## 5 ## is an S-prime and ## 25=5\cdot 5 ## is an S-composite.

(2) Now assume the statement is true for ## k\geq 1 ##. Then ## k_{i}=s+1 ## for ## s\geq 1 ##.

Observe that

\begin{align*}

&n=p_{1}^{s_{1}+1}p_{2}^{s_{2}+1}\dotsb p_{r}^{s_{r}+1}\implies\\

&n=p_{1}^{s_{1}}\cdot p_{1}\cdot p_{2}^{s_{2}}\cdot p_{2}\dotsb p_{r}^{s_{r}}\cdot p_{r}.\\

\end{align*}

Thus ## n=(p_{1}^{s_{1}}p_{2}^{s_{2}}\dotsb p_{r}^{s_{r}})(p_{1}p_{2}\dotsb p_{r}) ##.

Therefore, every S-composite can be expressed as a product of S-primes.

This completes the proof by strong induction.

Suppose ## p ## is an S-prime.

Then ## p=4k+1 ## for some ## k\in\mathbb{N} ##.

Let ## n ## be an S-composite such that ## n=p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{r}^{k_{r}} ## where ## p_{i} ## are all S-primes.

(1) When ## k=1 ##, the statement is ## p=4(1)+1=5 ##, which is true, because ## 5 ## is an S-prime and ## 25=5\cdot 5 ## is an S-composite.

(2) Now assume the statement is true for ## k\geq 1 ##. Then ## k_{i}=s+1 ## for ## s\geq 1 ##.

Observe that

\begin{align*}

&n=p_{1}^{s_{1}+1}p_{2}^{s_{2}+1}\dotsb p_{r}^{s_{r}+1}\implies\\

&n=p_{1}^{s_{1}}\cdot p_{1}\cdot p_{2}^{s_{2}}\cdot p_{2}\dotsb p_{r}^{s_{r}}\cdot p_{r}.\\

\end{align*}

Thus ## n=(p_{1}^{s_{1}}p_{2}^{s_{2}}\dotsb p_{r}^{s_{r}})(p_{1}p_{2}\dotsb p_{r}) ##.

Therefore, every S-composite can be expressed as a product of S-primes.

This completes the proof by strong induction.