# Proving an integer is composite

ver_mathstats
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.

Mentor
2022 Award
Are there even numbers among them?

• scottdave, topsquark and PeroK
Gold Member
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?

• ver_mathstats and topsquark
ver_mathstats
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

Mentor
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.

• ver_mathstats and topsquark
Homework Helper
Gold Member
2022 Award
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.

• topsquark
ver_mathstats
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

Homework Helper
Gold Member
2022 Award
i am not the best with proofs unfortunately
can you prove that one of ##9a+1## and ##9a +2## is composite?

• topsquark
Gold Member
Ok, I guess I overcomplicated it. @ver_mathstats : Have you tried to just generate quartets using different values of a?

ver_mathstats
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

Mentor
2022 Award
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.

Homework Helper
Gold Member
2022 Award
yes I have, and i get some prime numbers
Have you found ##a## where all four numbers are prime?

• WWGD and scottdave
Mentor
For a given value of a, look at two cases: one where a is even and the other where a is odd.

• scottdave and malawi_glenn
Staff Emeritus
• 