Prove that there exist infinitely many integers $k$ such that $k$ is not divisible by 5 and $12k+5$ is composite
Prove: there exist infinitely many integers $k$ such that $k$ is not divisible by 5 and $12k+5$ is composite
-
0If 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
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.
-
0Bill'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
$\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
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
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
-
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