Proving an integer is composite

In summary, the conversation discusses a problem that involves finding composite numbers among a set of expressions. The participants suggest using the Euclidean Algorithm and a proof by contradiction approach, but ultimately advise playing around with the expressions to find patterns. They also mention looking at the even-ness and odd-ness of the numbers in the set, particularly when considering different values of a.
  • #1
ver_mathstats
260
21
Homework Statement
Let a be an integer equal or greater than 0. Prove that at least one of the integers 9a+1, 9a+10, 9a+19 and 9a+28 is composite
Relevant Equations
euclidean algorithm
I am really struggling in how to begin this problem. So far I have considered using the Euclidean Algorithm and trying to find the gcd of each number like gcd(9,10) but each time they give me 1 so that doesn't work. My next idea is to do a proof by contradiction where I start with assuming that the integers are prime and somehow find a contradiction but I am unsure how to proceed.

Any help would be appreciated as I am really unsure of how to proceed. Thank you.
 
Physics news on Phys.org
  • #2
Are there even numbers among them?
 
  • Like
Likes scottdave, topsquark and PeroK
  • #3
There's some overlap. To the effects of the problem, all those are the same mod9:
9a+10=(9a+1)+9, etc.
Are you sure you're using the right numbers?
 
  • Like
Likes ver_mathstats and topsquark
  • #4
WWGD said:
There's some overlap. To the effects of the problem, all those are the same mod9:
9a+10=(9a+1)+9, etc.
Are you sure you're using the right numbers?
Yes this is the question I was given
 
  • #5
Three of the numbers in the set 9a+1, 9a+10, 9a+19 and 9a+28 seem to me to be red herrings that aren't essential to the problem. The sequence ##\{9a + 1 | a \ge 0\}## contains as subsets the sequences that are generated by the other three expressions. A previous hint asking whether some members of the sequence are even might be helpful.
 
  • Like
Likes ver_mathstats and topsquark
  • #6
ver_mathstats said:
Yes this is the question I was given
I'm struggling to see why you're struggling. It's difficult to give a hint without giving away the answer.

That said, the problem looks suspiciously easy.
 
  • Like
Likes topsquark
  • #7
PeroK said:
I'm struggling to see why you're struggling. It's difficult to give a hint without giving away the answer.

That said, the problem looks suspiciously easy.
i am not the best with proofs unfortunately
 
  • #8
ver_mathstats said:
i am not the best with proofs unfortunately
can you prove that one of ##9a+1## and ##9a +2## is composite?
 
  • Like
Likes topsquark
  • #9
Ok, I guess I overcomplicated it. @ver_mathstats : Have you tried to just generate quartets using different values of a?
 
  • #10
WWGD said:
Ok, I guess I overcomplicated it. @ver_mathstats : Have you tried to just generate quartets using different values of a?
yes I have, and i get some prime numbers
 
  • #11
ver_mathstats said:
yes I have, and i get some prime numbers
It is not about getting prime numbers. You said that you were looking for the existence of composite numbers. Therefore, look at even numbers, and make sure they are at least divisible by 4. You only have to find some, neither all nor none.
 
  • #12
ver_mathstats said:
yes I have, and i get some prime numbers
Have you found ##a## where all four numbers are prime?
 
  • Like
Likes WWGD and scottdave
  • #13
For a given value of a, look at two cases: one where a is even and the other where a is odd.
 
  • Like
Likes scottdave and malawi_glenn
  • #14
ver_mathstats said:
i am not the best with proofs unfortunately
Don't worry about a formal proof initially. Just play around with these expressions, somewhat systematically.

What can you say about the even-ness / odd-ness of ##9a## if ##a## is even?

What can you say about the even-ness / odd-ness of ##9a## if ##a## is odd?
 
  • Like
Likes WWGD, scottdave and PeroK

1. How do you prove that an integer is composite?

To prove that an integer is composite, you need to show that it has at least one factor other than 1 and itself. This can be done by finding two smaller numbers that multiply to equal the given integer.

2. Can you use any method to prove an integer is composite?

There are several methods that can be used to prove an integer is composite. Some common methods include trial division, the Sieve of Eratosthenes, and the AKS primality test.

3. Is it possible for an integer to be both prime and composite?

No, an integer cannot be both prime and composite. Prime numbers have exactly two factors (1 and itself), while composite numbers have more than two factors. Therefore, an integer cannot fulfill both criteria.

4. What is the difference between a prime and a composite number?

A prime number is a positive integer that has exactly two factors, 1 and itself. On the other hand, a composite number is a positive integer that has more than two factors. In other words, a composite number can be broken down into smaller factors, while a prime number cannot.

5. How does proving an integer is composite relate to number theory?

Proving an integer is composite is an important concept in number theory. Number theory is a branch of mathematics that deals with the properties and relationships of numbers. Proving an integer is composite helps us understand the fundamental building blocks of numbers and their characteristics.

Similar threads

  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
827
  • Calculus and Beyond Homework Help
Replies
3
Views
79
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
19
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
738
Replies
18
Views
2K
Back
Top