Omid Hatami wrote: Prove that there exists infinitely many primes $ p$ such that: \[ 13|p^3 + 1 \] It goes straight from Diriclet's theorem about primes in a arithmetic sequence. But I think I need a simple solution in a mathematical contest . Here is my solution . Easy to check that $ 13|p^3 + 1 \Leftrightarrow p\equiv \{12,10,4\} (\mod 12)$ Suppose there exist only finite prime have one of the form $ 12 + 13k,10 + 13k,4 + 13k$ Exist an integer $ n_0$ such that for all $ p\geq n_0$ then p hasn't these forms. Call $ p_1,...,p_t$ is all primes have one of the form $ 13k + 12,13k + 10,13k + 4$ Result 1 13 is a quadric reside mod p iff $ p(\mod 13)$ is $ {1,12,3,10,4,9\}}$ Result 2 $ 3^x (\mod 13) \in\{1,3,9\}$ Call $ A$ is set of prime in these forms 1$ 13k + 1,13k + 3,13k + 9$ Now consider the number $ A_k = (13\prod_{i = 1}^t p_i + 2)^2 - 13$ Easy to check that $ A_k\equiv 4 (\mod 13)$ If $ A_k$ has prime only in these form $ 13k + 1,13k + 3,13k + 9$ then exist an natural x such that $ A\equiv 3^x (\mod 13 )$ it gives $ A_k$ in A ,this is contradiction . So have many primes satisfy condition .

Can I get a full solution if I use Dirichlet's Theorem?

Johan Gunardi wrote: Can I get a full solution if I use Dirichlet's Theorem?

My teacher says, that if we know a know theorem(e.g. Dirichlet's), which leads to a solution, we can just write it. But this is a national olympiad so the situation is a little different, because your teacher cannot "defend" your solution.... Anyhow I would write that solution down, and try to come up with a solution like TTsphn's when/if I had finished the rest of the problems..