# Questions tagged [prime-numbers]

Prime numbers are natural numbers greater than 1 not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

10,340 questions
Filter by
Sorted by
Tagged with
107 views

### If $f$ and $g$ are nonzero polynomials with $\deg f>\deg g$, and if $pf+g$ has a rational root for infinitely-many primes $p$, then …

An IMO shortlist polynomial problem: Let $f$ and $g$ be two nonzero polynomials with integer coefficients and $\deg f>\deg g$. Suppose that for infinitely many primes $p$ the polynomial $pf+g$ has ...
61 views

### Primality test for specific class of $N=k \cdot 2^n+1$

Can you prove or disprove the following claim: Let $N=k \cdot 2^n+1$ be a natural number that is not a perfect square such that $2 \nmid k$ , $n>2$ . Let $c$ be the smallest odd prime number such ...
966 views

### Where can I find the modern proof of the prime number theorem?

Terence Tao described a modern proof of the prime number theorem in a lecture in UCLA, which is stated in wiki(enter link description here). From wiki: In a lecture on prime numbers for a general ...
75 views

118 views

### Does $\Phi_n(\alpha)=0$ in $\Bbb{F}_p$ for some $\alpha\in\mathbb{F}_p$ imply that $\mathrm{ord}(\alpha) = n$?

Let $\Phi_n(x)$ denote the $n^\text{th}$ cyclotomic polynomial. Suppose it has a root $\alpha$ in the finite field $\Bbb{F}_p$ and $p \nmid n$. Does it follow that $\mathrm{ord}(\alpha) = n$? In the ...
3k views

### Why are the last two numbers of this sequence never prime?

I had the idea to make a script that generates a pattern like this: 1 2 3 4 5 6 7 8 9 10 ... and so on. After that, I replaced every non-prime by a '-' ...
152 views

### A mysterious prime number 127

127 is probably the LAST / LARGEST prime number p such that $p^2$ mod q has an odd residue, where q is the previous prime number right before p. I have checked it up to $10^6$ , and it turned out to ...
22 views

### Asymptotic lower bound for the prime counting function, $\pi(x)?$

Consider a function that attempts to count primes up to a given $x$:$$\varphi(x)=\int_2^x \frac{1}{\log(t)}e^{-\frac{1}{\sqrt{t}}}~dt$$ Is $\varphi(x)$ an asymptotic lower bound to the prime counting ...
114 views

### Prime numbers which divide $n^3-3n+1$

Let $f(n)=n^3-3n+1$. It can be proved that for any prime $p$ and integer $n$ such that $p\mid f(n)$ we have either $p=3$ or $p\equiv\pm1\pmod 9$ (see below). Indeed, suppose that for prime number $p$ ...
113 views

### Is $N=2^{2^n}+2^{2^{n-1}}+2^{2^{n-2}}+2^{2^{n-3}} + \ldots+ 2^{2^3}+2^{2^2}+n$ is always composite?

Is number of the following form is always composite: $$N=2^{2^n}+2^{2^{n-1}}+2^{2^{n-2}}+2^{2^{n-3}} + . . . 2^{2^3}+2^{2^2}+n$$ I found similar question for $2^{2^n}+5$ . My attempt: We can rewrite N ...