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

• Math100
In summary, the proof by strong induction shows that every S-composite can be expressed as a product of S-primes. The induction hypothesis states that all elements of S that are smaller than or equal to 4*N+1 are either S-primes or a product of S-primes. The smallest S-composite is 25, which is a product of S-primes. The induction step involves assuming that the statement is true for k≥1 and showing that 4*(N+1)+1 is either an S-prime or a product of S-primes. If it is an S-prime, then there is nothing to do. Otherwise, it has a divisor d∈S that is neither 1 nor n
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.

Math100 said:
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.

Math100 said:
Suppose ## p ## is an S-prime.
I don't think the previous line is necessary. You don't do anything with this specific ##p.##
Math100 said:
Then ## p=4k+1 ## for some ## k\in\mathbb{N} ##.
Math100 said:
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.
Math100 said:
(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 ...
Math100 said:
... and ## 25=5\cdot 5 ## is an S-composite.
... a product of ##S##-primes. (Induction base: check.)
Math100 said:
(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##.

Last edited:
fresh_42 said:
I don't think the previous line is necessary. You don't do anything with this specific ##p.##

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 ##?

Math100 said:
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.##
Math100 said:
But the smallest example would be ## N=5 ##.
The smallest is now irrelevant. We already have the induction base: ##25=5\cdot 5.##
Math100 said:
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!

fresh_42 said:
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?

Math100 said:
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.

fresh_42 said:
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?

Math100 said:
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?

Math100 said:
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
fresh_42 said:
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) ##.

Math100 said:
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?

fresh_42 said:
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 ...
Math100 said:
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.

Math100

1. What is an S-composite?

An S-composite is a positive integer that can be expressed as a product of two or more positive integers other than 1 and itself.

2. What is an S-prime?

An S-prime is a positive integer that cannot be expressed as a product of two or more positive integers other than 1 and itself.

3. How do you express an S-composite as a product of S-primes?

To express an S-composite as a product of S-primes, you need to find all the prime factors of the S-composite number and then rearrange them as a product. For example, the S-composite number 24 can be expressed as 2 x 2 x 2 x 3, which is the product of the S-primes 2 and 3.

4. Is every S-composite number unique in its expression as a product of S-primes?

No, some S-composite numbers can have multiple expressions as a product of S-primes. For example, the S-composite number 30 can be expressed as 2 x 3 x 5 or 2 x 5 x 3, both of which are valid expressions.

5. Why is it important to express S-composites as a product of S-primes?

Expressing S-composites as a product of S-primes helps in understanding the fundamental building blocks of numbers and their relationships. It also has applications in number theory, cryptography, and other fields of mathematics.

Replies
5
Views
996
Replies
19
Views
929
Replies
14
Views
1K
Replies
4
Views
2K
Replies
12
Views
2K
Replies
10
Views
1K
Replies
4
Views
1K
Replies
10
Views
1K
Replies
6
Views
2K
Replies
4
Views
2K