Every S-composite can be expressed as a product of S-primes

[Math100]

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.

 

[fresh_42]

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.

I don't think the previous line is necessary. You don't do anything with this specific $p.$

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

We already know this.

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.

That is what we want to prove:
$n$ is $S$-composite $\Longrightarrow n=p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{r}^{k_{r}}$ where $p_{i}$ are all $S$-primes.

You cannot "let" the statement be true.

(1) When $k=1$, the statement is $p=4(1)+1=5$, which is true, because $5$ is an S-prime

You cannot read from $k$ whether $4k+1$ is an $S$-prime or an $S$-composite.

The induction base is the smallest $S$-composite. $\{1,5,9,13,17,21\}$ are all $S$-primes, so $25$ is the smallest $S$-composite ...

... and $25=5\cdot 5$ is an S-composite.

... a product of $S$-primes. (Induction base: check.)

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

You cannot perform the induction along the powers because as soon as you write $n$ in such a way you either already use the statement which we want to prove, or you use the ordinary prime factorization which doesn't tell us whether the primes are elements of $S$. For example $21=3\cdot 7 \in S$ but $3,7\not\in S.$

Let us formulate the induction hypothesis this way:

Assume all elements of $S$ that are smaller than or equal to $4\cdot N +1$ are either $S$-primes or a product of $S$-primes.

(Induction hypothesis: check.)

Now, we need to show that $4\cdot (N+1)+1$ is either an $S$-prime or a product of $S$-primes.

(Statement that has to be proven: check.)

If it is an $S$-prime then there is nothing to do.
So assume $n:=4\cdot (N+1)+1$ is an $S$-composite.

This means that it has a divisor $d\in S$ that is neither $1$ nor $n$.
Say $d=(4k+1) \,|\,n$ with $0<k\leq N.$ We can do this because $d\in S.$

Can you write $n$ as a product of $S$-primes?

Hint: write $n=d\cdot e$ and use the induction hypothesis on $d$ and $e$.

 

[Math100]

I don't think the previous line is necessary. You don't do anything with this specific $p.$

We already know this.

That is what we want to prove:
$n$ is $S$-composite $\Longrightarrow n=p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsb p_{r}^{k_{r}}$ where $p_{i}$ are all $S$-primes.

You cannot "let" the statement be true.

You cannot read from $k$ whether $4k+1$ is an $S$-prime or an $S$-composite.

The induction base is the smallest $S$-composite. $\{1,5,9,13,17,21\}$ are all $S$-primes, so $25$ is the smallest $S$-composite ...

... a product of $S$-primes. (Induction base: check.)

You cannot perform the induction along the powers because as soon as you write $n$ in such a way you either already use the statement which we want to prove, or you use the ordinary prime factorization which doesn't tell us whether the primes are elements of $S$. For example $21=3\cdot 7 \in S$ but $3,7\not\in S.$

Let us formulate the induction hypothesis this way:

Assume all elements of $S$ that are smaller than or equal to $4\cdot N +1$ are either $S$-primes or a product of $S$-primes.

(Induction hypothesis: check.)

Now, we need to show that $4\cdot (N+1)+1$ is either an $S$-prime or a product of $S$-primes.

(Statement that has to be proven: check.)

If it is an $S$-prime then there is nothing to do.
So assume $n:=4\cdot (N+1)+1$ is an $S$-composite.

This means that it has a divisor $d\in S$ that is neither $1$ nor $n$.
Say $d=(4k+1) \,|\,n$ with $0<k\leq N.$ We can do this because $d\in S.$

Can you write $n$ as a product of $S$-primes?

Hint: write $n=d\cdot e$ and use the induction hypothesis on $d$ and $e$.

If $n=4\cdot (N+1)+1$, then $n$ can be expressed as a product of S-primes. But the smallest example would be $N=5$. If we write $n=d\cdot e$, then how can we show that $d, e$ are S-primes? Do we use substitution of $4\cdot N+1$?

 

[fresh_42]

If $n=4\cdot (N+1)+1$, then $n$ can be expressed as a product of S-primes.

No. This is still the wrong logic. We know that the statement is true for $1,5,\ldots,4N+1.$ We do not know that it is true for $n.$

But the smallest example would be $N=5$.

The smallest is now irrelevant. We already have the induction base: $25=5\cdot 5.$

If we write $n=d\cdot e$, then how can we show that $d, e$ are S-primes? Do we use substitution of $4\cdot N+1$?

No. $d$ and$e$ are not $S$-primes, at least not necessarily. However, we know that $d<n$ and $e<n$. For numbers that are smaller, we have the induction hypothesis! And we have it for all such numbers which is why we use strong induction. Apply the induction hypothesis! Twice!

 

[Math100]

No. This is still the wrong logic. We know that the statement is true for $1,5,\ldots,4N+1.$ We do not know that it is true for $n.$

The smallest is now irrelevant. We already have the induction base: $25=5\cdot 5.$

No. $d$ and$e$ are not $S$-primes, at least not necessarily. However, we know that $d<n$ and $e<n$. For numbers that are smaller, we have the induction hypothesis! And we have it for all such numbers which is why we use strong induction. Apply the induction hypothesis! Twice!

So since $d=(4k+1)\mid n$, we have $(4k+1)a=n\implies (4k+1)a=d\cdot e$. How should I apply the induction hypothesis?

 

[fresh_42]

So since $d=(4k+1)\mid n$, we have $(4k+1)a=n\implies (4k+1)a=d\cdot e$. How should I apply the induction hypothesis?

A proof by induction always follows the scheme:
Induction base - here: $25=5\cdot 5$
Induction hypothesis - here: All elements of ##S## that are smaller than or equal to $4N+1$ are either ##S##-primes or a product of ##S##-primes.

Induction step: Show that the next greater element than $4N+1$ which is $4N+5$ is either $S$-prime or a product of $S$-primes, too.

Case 1: $4N+5$ is $S$-prime, then is nothing to do, and we look for the next greater $S$-composite. This would be

Case 2: $4N+5$ is $S$-composite (or some other, greater value for $N$).

$S$-composite means it has a divisor $d\in S.$
Thus $n=4N+5=d\cdot e$ with $d,e\in S-\{1,n\}.$

Here is the clue now:

Because $d$ and $e$ are smaller than $n$, the induction hypothesis says, that they are either $S$-prime or product of $S$-primes. In formulas:
$$
d=p_1^{i_1}\cdot\ldots\cdot p_r^{i_r} \;\text{ and }\;e=p_1^{j_1}\cdot\ldots\cdot p_s^{j_s}
$$
where $r,s \geq 1,$ $i_k,j_k>0,$ and all $p_i \in S.$

All that is left to do is write $n=d\cdot s =p_1^{i_1}\cdot\ldots\cdot p_r^{i_r}\cdot p_1^{j_1}\cdot\ldots\cdot p_s^{j_s}$ which is a product of $S$-primes again. And that had to be shown.

 

[Math100]

A proof by induction always follows the scheme:
Induction base - here: $25=5\cdot 5$
Induction hypothesis - here: All elements of ##S## that are smaller than or equal to $4N+1$ are either ##S##-primes or a product of ##S##-primes.

Induction step: Show that the next greater element than $4N+1$ which is $4N+5$ is either $S$-prime or a product of $S$-primes, too.

Case 1: $4N+5$ is $S$-prime, then is nothing to do, and we look for the next greater $S$-composite. This would be

Case 2: $4N+5$ is $S$-composite (or some other, greater value for $N$).

$S$-composite means it has a divisor $d\in S.$
Thus $n=4N+5=d\cdot e$ with $d,e\in S-\{1,n\}.$

Here is the clue now:

Because $d$ and $e$ are smaller than $n$, the induction hypothesis says, that they are either $S$-prime or product of $S$-primes. In formulas:
$$
d=p_1^{i_1}\cdot\ldots\cdot p_r^{i_r} \;\text{ and }\;e=p_1^{j_1}\cdot\ldots\cdot p_s^{j_s}
$$
where $r,s \geq 1,$ $i_k,j_k>0,$ and all $p_i \in S.$

All that is left to do is write $n=d\cdot s =p_1^{i_1}\cdot\ldots\cdot p_r^{i_r}\cdot p_1^{j_1}\cdot\ldots\cdot p_s^{j_s}$ which is a product of $S$-primes again. And that had to be shown.

After writing that Case 1, where $4N+5$ is S-prime, do we have to explain anything in the proof? Or just go straight to the Case 2? Also, what's the difference between proof by induction and proof by strong induction?

 

[fresh_42]

After writing that Case 1, where $4N+5$ is S-prime, do we have to explain anything in the proof? Or just go straight to the Case 2? Also, what's the difference between proof by induction and proof by strong induction?

You can write: Assume w.l.o.g. (without loss of generality) that $n$ is $S$-composite.

Since we didn't impose any restrictions on $n$ or $N$ and we don't have to prove anything for $S$-primes, we can directly assume that $n$ is $S$-composite.

 

[Math100]

Another (second part) of the question in this same problem asks:
Give an example of an S-composite that can be expressed as a product of S-primes in more than one way.

So I was thinking of such an example as $81$, since $81=9\cdot 9$ is an S-composite. But I do not really understand what the question is completely asking for when it mentions "in more than one way". What does this mean and how can $81$ be expressed as a product of S-primes in more than one way?

 

[fresh_42]

Another (second part) of the question in this same problem asks:
Give an example of an S-composite that can be expressed as a product of S-primes in more than one way.

So I was thinking of such an example as $81$, since $81=9\cdot 9$ is an S-composite. But I do not really understand what the question is completely asking for when it mentions "in more than one way". What does this mean and how can $81$ be expressed as a product of S-primes in more than one way?

They ask for a number $(4a+1)\cdot (4b+1) = n = (4c+1)\cdot (4d+1)$ with all $S$-primes. Maybe longer decompositions.

Remember that we have a lot more $S-$primes than we have primes. $21$ looks like a promising candidate to use as a factor.

 

[Math100]

They ask for a number $(4a+1)\cdot (4b+1) = n = (4c+1)\cdot (4d+1)$ with all $S$-primes. Maybe longer decompositions.

Remember that we have a lot more $S-$primes than we have primes. $21$ looks like a promising candidate to use as a factor.

So $n=441=21\cdot 21$ would work in here? $441=(4a+1)(4b+1)=(4c+1)(4d+1)$.

 

[fresh_42]

So $n=441=21\cdot 21$ would work in here? $441=(4a+1)(4b+1)=(4c+1)(4d+1)$.

It should work. Can you express $21\cdot 21$ with another decomposition into $S-$primes?

 

[Math100]

It should work. Can you express $21\cdot 21$ with another decomposition into $S-$primes?

Will that be $441=21\cdot 21=(4a+1)(4b+1)=9\cdot 49$ where $a=2, b=12$?

 

[fresh_42]

Yes, that was what was asked. $9,21,49$ are all $S$-primes, and ...

Will that be $441=21\cdot 21=(4a+1)(4b+1)=9\cdot 49$ where $a=2, b=12$?

... are two different compositions.

Ordinary prime number decompositions are unique.