Let k is integer which is not a cube. If there exists a prime p [respectively infinitely many primes p] congruent to 3 modulo 8 and such that k is not a cube modulo p? Thanks in advance for proof or counterexample!

$\begingroup$ If you do not mind, could you say a little in which context this question arose/why you are interested in this. Some people find it helpful to have such information alongside with the actual question. $\endgroup$ – user9072 Feb 11 '12 at 23:18

3$\begingroup$ Have you tried applying the Chebotarev density theorem to a suitable extension $\mathbf{Q}(k^{1/3}, \alpha)/\mathbf{Q}$? $\endgroup$ – TKe Feb 11 '12 at 23:25

1$\begingroup$ (Hint: For $p \equiv 3 \pmod{8}$ look at cyclotomic extensions; you also have to adjoin a 3rd root of unity to make the extension Galois.) $\endgroup$ – TKe Feb 11 '12 at 23:32
Your condition $p \equiv 3 \pmod 8$ is unusual, everything is a cubic residue $\pmod 3$ and $\pmod q$ where $q \equiv 2 \pmod 3.$ However, Timo seems to have this well in hand.
This is just a bit of culture. A rational number is a square if and only if it is a square in every $\mathbb Q_p$ for all $p \leq \infty.$
I got a bit frustrated thinking about the analogous statement for cubes, but it works. In GSS it is proved that, if a polynomial in one variable with integer coefficients has prime degree, if it is reducible in all $\mathbb Q_p,$ then it is reducible in $\mathbb Q.$ In particular, the polynomial $x^3 k$ is irreducible in $\mathbb Q$ if $k$ is not a cube. As the degree is 3, a prime, $x^3 k$ is irreducible in some $\mathbb Q_p,$ meaning that there is no linear factor and no root, as $3 = 1 + 2.$ Finally, by Hensel's lemma, $k$ is not a cubic residue $\pmod p.$
Language in the article (mentioning Chebotarev density) suggests that the direction I use, prime degree, was known for quite some time, that the news in the article is about composite degree.
The laughter may now commence.

$\begingroup$ Will, the GrunwaldWang Theorem states that "global $n$th power" equals "locally everywhere $n$th power", and usually equals "locally almosteverywhere $n$th power" (with the exceptions precisely demarcated). $\endgroup$ – B R Feb 12 '12 at 1:30

$\begingroup$ @BR, thanks, I found this: en.wikipedia.org/wiki/Grunwald%E2%80%93Wang_theorem $\endgroup$ – Will Jagy Feb 12 '12 at 2:47

$\begingroup$ Thanks! I see that by GrunwaldWang Theorem: if k is not a cube in Q then k is not a cube modulo infinitely many primes p. But what with my extra condition "p is congruent to 3 modulo 8" (or similar congruences modulo power of 2)? Is it breaking nothing? $\endgroup$ – jan Feb 13 '12 at 9:41

1$\begingroup$ @jan, the collective opinion of the experts here seems to be that you ought to know how to do this yourself, if you are engaged in research that requires this. Timo told you how to apply Chebotarev density. If you don't know how to finish that argument (I do not), your best bet is to place a more detailed question at math.stackexchange.com/questions?sort=active in which you say exactly why you care about $3 \pmod 8,$ say what GrunwaldWang gives and what it does not, but mostly detailing your background. $\endgroup$ – Will Jagy Feb 13 '12 at 20:34