Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that there exist infinitely many integers $k$ such that $k$ is not divisible by 5 and $12k+5$ is composite

share|cite|improve this question
The question does not make sense. Because the assumption mentions $k$ explicitly, one has to interpret the consequent as being about the same particular $k$ that satisfied the assumption -- however, once $k$ is given there is only one number of the form $12k+5$, whether divisible by 5 or not -- namely $12k+5$ itself. – Henning Makholm Sep 9 '11 at 11:52
@Henning Makholm I might have made a mistake. The question might have been "Prove that if k (integer) is not divisible by 5 then there exists an infinite amount of COMPOSITE numbers of the form 12k + 5. Does that make more sense? – evodevo Sep 9 '11 at 12:44
no. The problem is still that your formulation seems to ask for an infinite number of solutions for each particular $k$. But as soon as $k$ is given, $12k+5$ is only one number (which may not even be composite). – Henning Makholm Sep 9 '11 at 12:48
You could validly ask "Prove that there exists infinitely many composite numbers of the form $12k+5$ that are not divisible by $5$", or equivalently "Prove that there exist infinitely many $k$ such that $k$ is not divisible by 5 and $12k+5$ is composite". – Henning Makholm Sep 9 '11 at 12:52
@Henning Makholm What about "For each k which is an integer not divisible by 5 there exists a composite number of the form 12k + 5"? – evodevo Sep 9 '11 at 13:16

Prove that there exist infinitely many integers k such that k is not divisible by 5 and 12k+5 is composite

For every $K$ there is a $k>K$ that works. Choose $k_0>K$ such that $k_0$ is not divisible by 5. If $12k_0+5$ is composite, then we're done. Otherwise $12k_0+5$ is a prime $p$. Then $12(p+k_0)+5 = 13p$ is composite, and $p+k_0$ cannot be divisible by $5$, because then $13p$ would also be.

share|cite|improve this answer
Malkholm can you prove the same using mathematical induction or other alternative method? – evodevo Sep 15 '11 at 18:46
Bill's answer is an "alternative method", isn't it? One could probably adapt it to contain an explicit induction (most likely on $n$), but I'm not sure doing so would be particularly illuminating. – Henning Makholm Sep 15 '11 at 18:59

$\rm\: f_n = 17\cdot 13^{\:n}$ are all composite. $\rm\: 5\nmid f_n,\ \: f_n \equiv\: 5\pmod{12}\:,\:$ so $\rm\ f_n = 5 + 12\ k\:,\ \ 5\nmid\:k\ \ $ QED

How did I find that? $\: $ Hint: $\:$ mod $\rm\: 12:\ a\:\equiv\:5,\:\ b\:\equiv\:1 \ \Rightarrow\ a\:b^n\:\equiv\: 5\:,\:$ i.e. integers of the form $\rm\:12\:k+5\:,\:$ e.g. $17$, do remain of that form when multiplied by integers of form $\rm\:12\:n+1\:,\:$ e.g. $\:13\:.$ Per request, without congruences, $\rm\ (12\:k+r)\:(12\:n+1)\ =\ 12\ (12\:k\:n+r\:n+k)+r\:,\:$ therefore we easily deduce by induction that $\rm\:(12\:k+r)\:(12\:n+1)^k\:$ has form $\rm\:12\:m+r\:.$

NOTE $\ $ Alternatively once may proceed as follows.

Note $\rm\qquad\ 7\ $ divides $\rm\ 12\ (35\ n-1) + 5\ \ $

Also $\rm\qquad 11\ $ divides $\rm\ 12\ (55\ n + 6) + 5 $

and $\ \rm\qquad 13\ $ divides $\rm\ 12\ (65\ n - 8) + 5 $

and $\ \rm\qquad 17\ $ divides $\rm\ 12\ (85\ n + 1) + 5\ \ $
$\qquad\qquad\quad\qquad\ \cdots$
and $\rm\qquad\ \ \: d\ $ divides $\rm\ 12\ (5d\ n + k) + 5\ \ $ for any $\rm\ d\:$ coprime to $\rm\:30\:,\:$ $\rm\ k \equiv\: {-}5/12\pmod{d}$

Notice: $\rm\ \ \ d\:$ coprime to $\rm\:2,3\ \Rightarrow\ d\:$ coprime to $12\:,\:$ therefore we infer $\rm\: 1/12\: $ exists $\rm\: (mod\ d)\:.\:$

Further: $\rm\ d\:$ coprime to $\rm\:5\ \Rightarrow\ k\:$ or $\rm\:k+d\:$ is coprime to $5\ $ (otherwise $\rm\ 5\:|\:k,k+d\ \Rightarrow\ 5\:|\:d\:)$

E.g. $\rm mod\ d = 11,\ \dfrac{-5}{12}\:\equiv\: {-}5\:;\:$ $\rm\: {-}5+11\ $ is coprime to $\:5\:.$

share|cite|improve this answer
@evo What is not clear? The first line is a complete proof. You can ignore the alternative method in the note if so desired. – Bill Dubuque Sep 16 '11 at 23:29
I don't get how one argument follows from the other. Can you rewrite it without congruence relations? – evodevo Sep 17 '11 at 0:14
The note is not related to the first proof. You can rewrite $a\equiv b\pmod n$ as $n$ divides $a−b$ or, equivalently, $a=b+k\:n$ for some integer $k$. Said without congruences, the gist of the first proof is that $(12\:j+5)(12\:k+1)^n$ has form $12\:m+5$. To help further I'll need to know precisely where you are stuck. – Bill Dubuque Sep 17 '11 at 1:26
Can you prove that (12j + 5)(12k + 1)^n has form 12m + 5 without using congruences? – evodevo Sep 19 '11 at 7:12
@evo See my recent edit above. – Bill Dubuque Sep 19 '11 at 12:34

For the new question, the easiest way to select some prime $p$ other than $2,3 $(the factors of $12$) and $5$ and ask for solutions modulo $p. 7$ comes to mind. If $k \equiv 6 \pmod {7}, 12k+5\ \ $ is divisible by $7$.

share|cite|improve this answer
+1 I'm now using an alternative method, so I removed the prior comment to avoid confusion. But I left the similar method as a note. – Bill Dubuque Sep 10 '11 at 0:14
@Ross Milikan How do you know that if k is divisible by 7 with remainder of 6, then 12k + 5 is divisible by 7? – evodevo Sep 18 '11 at 18:12
@evodevo: If $k=6 \pmod 7, 12k+5=12(-1)+5=-7=0 \pmod7$ – Ross Millikan Sep 19 '11 at 8:44
@Ross Milikan It doesn't seem to work with p=13. If k≡6(mod13),12k+5 doesn't seem to be divisible by 13. If k = 13n + 6 then 12(13n + 6) + 5 = 156n + 77 is not divisible by 13 because 77 is not divisible by 13. Or did I misunderstood it? – evodevo Sep 19 '11 at 21:14
@evodevo: you need to choose the multiplier based on the modulus. As $12=-1 \pmod {13}$, if $k=5 \pmod {13}, 12k+5=0 \pmod{13}$ – Ross Millikan Sep 20 '11 at 10:01

I second with Henning.

As for the question,

Since $k$ is not divisible by 5, it can only be congruent to 1,2,3 or 4 $\mod 5$. Since 5 does not divide 12 as well, the product $12k$ will never be divisible by 5.

So you have ALL numbers of the form $12 k + 5$ not divisible by 5, where $k$ is not divisible by 5.

Since 12k+5 is to be composite and k is not divisible by 5, suppose k=1 (mod 5). If k=6(mod 7), then 12k+7=12*6+5=77=0 (mod7).

Similar approach works for k=2,3,4(mod 5).

In general, pick up any prime other than 2,3,5- call it p.

Let k=s(mod p). Now, 12k+5=12s+5=0(mod p) as LHS is composite.

Now, there exists a s such that LHS is composite i.e. multiple of p where (12,p)=1..This follows from a theorem in elementary number theory. So there you are:

For any prime p and k not divisible by p, you can have the expression composite.

share|cite|improve this answer

Let $k=5t+r$ with $0<r<5$. Then $12k+5=2r+5(12t+2r)$. Now $2r$ is never a multiple of $5$ and so $12k+5$ is never a multiple of $5$ for any $t$.

share|cite|improve this answer
@evodevo, like Henning noted, your question could be better phrased. I answered this version: "prove there exists an infinite amount of numbers of the form $12k + 5$ which are not divisible by $5$ with $k$ not divisible by $5$". – lhf Sep 9 '11 at 11:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.