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

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

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

-
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\:.$

-
@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$.

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

-

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

-
@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