2
$\begingroup$

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

  • 0
    If you are looking for an infinite number of composite numbers of the form $12k+5$ which are not divisible by 5, here are some hints. First note that with $k=1$ the expression gives the answer 17. Can you see a way of adjusting $k$ to get a higher multiple of 17 (try adding the obvious number to $k$) - then an infinite number of multiples of 17. Now some of these may be divisible by$5$- which ones? If you exclude those can you show you still have infinitely many examples left?2011-09-09

5 Answers 5

4

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.

  • 0
    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.2011-09-15
4

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

  • 0
    @evo the point is that multiplication by $\rm\:12\:k+1\:$ doesn't alter a numbers remainder mod $12$, i.e. $\rm\:(12\:k+r)\:(12\:n+1)\:$ has form $\rm\:12\:m+r\:,\:$ i.e. it still has remainder $\rm\:r\:,\:$ see my new edit above. This is one non-congruence way of saying that $\rm\:r\cdot 1\equiv r\pmod{12}\:.$2011-09-19
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$.

  • 0
    @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}$2011-09-20
2

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.

1

Let $k=5t+r$ with $0. 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$.

  • 0
    @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$".2011-09-09