Every positive integer except 1 is a multiple of at least one prime.

In summary: It's not very good. Use mfb's suggestion and induction.In summary,The problem (and its solution) are attached in TheProblemAndSolution.jpg. Specifically, I am referring to problem (c).Homework EquationsSet theory.Union.Integers.Prime numbers.The Attempt at a SolutionI see how we have all multiples of all prime numbers in the union of the sets, but I can't see how “every positive integer except 1 is a multiple of at least one prime number”. If I could intuitively grasp the sentence I just quoted, then I can see how to get to the final result.
  • #1
s3a
818
8

Homework Statement


The problem (and its solution) are attached in TheProblemAndSolution.jpg. Specifically, I am referring to problem (c).

Homework Equations


Set theory.
Union.
Integers.
Prime numbers.

The Attempt at a Solution


I see how we have all multiples of all prime numbers in the union of the sets, but I can't see how “every positive integer except 1 is a multiple of at least one prime number”. If I could intuitively grasp the sentence I just quoted, then I can see how to get to the final result.

Any help in getting me to intuitively understand the part I quoted would be greatly appreciated!
 

Attachments

  • TheProblemAndSolution.jpg
    TheProblemAndSolution.jpg
    16.2 KB · Views: 582
Physics news on Phys.org
  • #2
Every positive integer except 1 is a multiple of at least one prime.
Isn't that a trivial statement given the definition of prime numbers?
Hint: look at the factors of the number.
 
  • #3
mfb said:
Isn't that a trivial statement given the definition of prime numbers?
Hint: look at the factors of the number.

It's not TOTALLY trivial. If a number ##n## isn't prime then it can be factored into ##n=ab## where neither ##a## nor ##b## is one. If neither one is prime then they are both composite and ##a<n##. Then factor ##a##. You need to argue that this can't go on forever. It's sort of intuitively obvious but to write a formal proof you need to say that there is not an infinite sequence of decreasing positive integers. There is a little meat here.
 
  • #4
Thanks for the replies.

I think I now understand it intuitively. Basically, prime numbers are numbers that can't be factored further (except for factors of 1 and the number itself), and all composite numbers can be divided by a prime number, since a prime number is at least one of the multiplicands of the factored form of the composite numbers, right?

Assuming I've understood the intuitive argument, I would like to move to the formal proof, so, Dick or mfb (or anyone else), could you please show me how you would (formally) prove that “every positive integer except 1 is a multiple of at least one prime number”?
 
  • #5
Dick said:
It's not TOTALLY trivial. If a number ##n## isn't prime then it can be factored into ##n=ab## where neither ##a## nor ##b## is one. If neither one is prime then they are both composite and ##a<n##. Then factor ##a##. You need to argue that this can't go on forever. It's sort of intuitively obvious but to write a formal proof you need to say that there is not an infinite sequence of decreasing positive integers. There is a little meat here.
I am aware of that, and still consider this as trivial. You can use induction as well.

s3a said:
I think I now understand it intuitively. Basically, prime numbers are numbers that can't be factored further (except for factors of 1 and the number itself), and all composite numbers can be divided by a prime number, since a prime number is at least one of the multiplicands of the factored form of the composite numbers, right?
Right.
Assuming I've understood the intuitive argument, I would like to move to the formal proof, so, Dick or mfb (or anyone else), could you please show me how you would (formally) prove that “every positive integer except 1 is a multiple of at least one prime number”?
Dick gave you one approach, induction is another possible way to prove it.
 
  • #6
s3a said:
Thanks for the replies.

I think I now understand it intuitively. Basically, prime numbers are numbers that can't be factored further (except for factors of 1 and the number itself), and all composite numbers can be divided by a prime number, since a prime number is at least one of the multiplicands of the factored form of the composite numbers, right?

Assuming I've understood the intuitive argument, I would like to move to the formal proof, so, Dick or mfb (or anyone else), could you please show me how you would (formally) prove that “every positive integer except 1 is a multiple of at least one prime number”?

I agree with mfb. If you think you understand it intuitively, you should start the proof, not us.
 
Last edited:
  • #7
Well, is it formal to say the following?:

Let any integer greater than 1, referred to by N, be the product of M_1, M_2, . . ., M_i, then N = M_1 * M_2 * . . . * M_i, where each multiplicand of N can be written the product of m_1 * m_2 * . . . * m_j, and so forth until the recursion ends and N is described by the product of numbers that can only be divided by themselves and the number 1, which includes all prime numbers and the number 1, but since multiplying any number by the number 1 doesn't affect the result, we can say that all positive integers greater than 1 can be written as the product of prime numbers.
Q.E.D.
 
  • #8
s3a said:
Well, is it formal to say the following?:

It's not very good. Use mfb's suggestion and induction. Suppose all integers less than or equal to N have a prime factor. Use that to prove all integers less than or equal to N+1 have a prime factor. Think about it and think about induction.
 

1. What does it mean for a number to be a multiple of a prime?

Being a multiple of a prime means that the number can be evenly divided by that prime number without any remainder.

2. Can you give an example of a number that is a multiple of a prime?

Yes, for example, the number 12 is a multiple of the prime number 2 because it can be divided evenly by 2 with no remainder.

3. Why is 1 not considered a multiple of a prime?

1 is not considered a multiple of a prime because it can only be divided by itself and 1, meaning it does not have any other prime factors.

4. How does this statement relate to the Fundamental Theorem of Arithmetic?

This statement is a direct result of the Fundamental Theorem of Arithmetic, which states that every positive integer can be expressed as a unique product of primes.

5. Why is it important to understand that every positive integer except 1 is a multiple of at least one prime?

Understanding this concept allows us to further understand the properties and relationships of numbers. It also helps in solving problems involving prime numbers and their multiples, such as in number theory and cryptography.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
754
  • Precalculus Mathematics Homework Help
Replies
24
Views
5K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
2K
  • Precalculus Mathematics Homework Help
2
Replies
35
Views
4K
Replies
8
Views
264
Replies
13
Views
1K
  • General Math
Replies
2
Views
965
Back
Top