I have a number theory question and i don't know what to begin with .
Show that for each prime , there exists a prime such that
is NOT divisible by for any positive integer .
Thanks a lot .
i'm not sure, i think there's a result which says if with has a root modulo every prime, then is reducible in if this is true, then your problem will be just a trivial
application of it. it's quite late now and my brain is not functioning anymore. so maybe someone can find a proof or a reference for that.
But does not imply that is a multiple of q.
The result is true for p=3, with q=7. If n is a multiple of 7 then clearly is not divisible by 7. If n is not a multiple of 7 then , and so . The same argument will work for any prime p such that q = 2p+1 is also prime. But I do not see how to extend it to the general case. Maybe that requires some more abstract argument such as NonCommAlg's.
Alas, the theorem seems to be false: http://tinyurl.com/yl25nob , and btw theorem 1 there appears to be really fascinating.
Tonio
Your question is asking if is solvable i.e. is a power residue modulo ?
Theorem: Let be a prime. If , then is an power residue modulo , where . Ask if you'd like to see why this is true.
Let . If , then we look at . But by flt. Thus we want .
Dirichlet tells us there's an infinite amount of primes of this form.
So we now know , but this isn't enough.
We need ... and now I'm stuck.
Edit: Opalg's post supports this: and .
that theorem actually proves my claim because the polynomial is irreducible (by Eisenstein's criterion) and its degree is a prime number. so, by that theorem it cannot be reducible
(and therefore cannot have a root) modulo every prime number.
today i talked to a friend of mine, who is a number theorist, about the result i mentioned and he confirmed my guess. he said that even a stronger result can be proved:
if has a root modulo every prime, then has a "linear factor" (as an element of ). this is a very interesting result!