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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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