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

learn more… | top users | synonyms

0
votes
1answer
14 views

Fermat's Little Theorem and prime divisors

Let $a,b\in\Bbb N$ and $a+b$ be an even number. Let $a^2 - b^2 - a$ is an exact square, say $c^2$. Let $m = \frac {a+b}2$ and $n = \frac {a-b}2$. Then, $$(4m-1)(4n-1) = 4(4mn-m-n) + 1 = ...
0
votes
1answer
54 views

Prove that for all $n\in \mathbb N$ $(n>1)$ the number $n^4+4^n$ is not prime. [duplicate]

Prove that for all $n\in\mathbb N$ $(n>1)$ the number $n^4+4^n$ is not prime. Can someone give me some pointers?
3
votes
0answers
16 views

Squarefree products of a class of primes

Numbers which are the sum of two squares are the product of a square and a collection of distinct primes which are 1 or 2 mod 4. Landau proved that there are $\sim kx/\sqrt{\log x}$ such numbers up ...
0
votes
0answers
19 views

Prove that If $p$ is an odd prime, then any divisor of the Mersenne number $M_p = 2^p − 1$ is of the form $2kp + 1$

For example, $M_{11} = (2 · 1 · 11 + 1)(2 · 4 · 11 + 1)$ If $q$ is a prime divisor of $M_p$ then $\exists k \in Z$ such that $qk = 2^p-1$. Now $ord(2,q)$ is the smallest positive integer $a$ such ...
0
votes
0answers
20 views

Motivation for $r$ in AKS Primality Test

I've been reading up on the AKS primality test, and I understand the big ideas and proofs as they are pretty elementary number theory. I am confused about how to value of $r$ is selected. In the ...
0
votes
1answer
31 views

Does there exist an integer $s$ such that every integer $> 1$ can be written as a sum of at most $s$ primes?

Does there exist an integer $s$ such that every integer $> 1$ can be written as a sum of at most $s$ primes ?
1
vote
1answer
26 views

If equation has integer solution it has solution for every prime p.

How to prove that if the equation in the form: $a_0 x_0^2 + a_1 x_1^2 + \dots + a_nx_n^2 = 0$ where $a_0, a_1, \dots , a_n \in \mathbb{Z}$, has an integer solution, then it has solution in ...
0
votes
2answers
32 views

Congruence for Stirling Number of first kind $s(n,k)$ when $n$ is prime

Let $s(n,k)$ be the Stirling numbers of first kind: $$\prod_{k=0}^{k=n-1}(x-k) =\sum_{k=0}^{k=n}s(n,k)x^k$$ $p$ is prime $\iff$ for all $k\in\{2,..,p-1\}$, $s(p,k)\equiv0\ mod\ p $ How ...
3
votes
3answers
95 views

Prove there exists $m > 2010$ such that $f(m)$ is not prime

Let $$f(x) = \sum_{i = 0}^n a_ix^i$$ be a polynomial with $a_i \in \mathbb Z, n > 0, a_n \neq 0$. Prove that there exists some natural number $m>2010$ such that $|f(m)|$ is not a prime number. ...
0
votes
1answer
25 views

A question in Number Theory - prove there exist m>2010 s.t f(m) is not prime [duplicate]

Let $$f(x)=\sum_{i=0}^n a_nx^n$$ be a polynomial with $$a_n \in Z,n>0,a_n\neq0$$ Prove that there exists some natural number $$m>2010$$ such that $$|f(m)|$$ is not a prime number. I tried to ...
0
votes
1answer
36 views

A question about primes, number theory [duplicate]

I tried to solve this question but without a success: Let $p$ be a prime number,and $p^2+2$ is also prime, prove that $p=3$. I tried to show $p^2+2$ as a product of numbers and then to show that ...
2
votes
1answer
26 views

Determine if n is a prime.

Let $n$ be a positive natural number. You know the following facts about $n$ . Firstly, $n<10^{6}$ . Moreover, not a single integer $k$ between $1$ and $10^{4}$ divides $n$ . Does it ...
1
vote
0answers
32 views

Marking Integers Using a Wheel

Suppose I had a wheel of diameter one meter and I was charged with marking every meter along an infinite stretch of a beach. The strategy is to insert pegs into the wheel so that every point that is a ...
1
vote
1answer
23 views

Is it possible to estimate the number of primes between 0 and a 128 bit number?

I'm attempting to visualize an RSA public/private key pair, or a SHA2 hash. In order to reduce that massive number that is meaningful to humans I'm looking at this SHA2 visualization function to ...
0
votes
1answer
37 views

Is n a prime if $n\in\mathbb{N}$, $n<10^{6}$ and $1<k<n$, $k\nmid n$

Can I get hints on how I can explain this? Question Let $n$ be a positive natural number. You know the following facts about $n$. Firstly, $n<10^{6}$. Moreover, not a single integer $k$ between ...
5
votes
0answers
50 views

An Impossible Sequence of Prime Powers

Let $x_1,x_2,\ldots$ be a sequence of positive integers that satisfies the recurrence relation $$x_{n+1}=2x_n(x_n-1)+1$$ for all positive integers $n$. It seems impossible that every term in this ...
1
vote
2answers
50 views

When is $n\choose k$ a multiple of $n$

While working through a question, the solution states that in the finite field $\mathbb{F}_p$ for $p$ prime, we have $(u+v)^p=u^p + v^p$ and since $(u+v)^p={p\choose 0}u^pv^0+{p\choose ...
0
votes
0answers
22 views

the asymptotic approximation of a sum

$p_{n}$ and $p_{j}$ are two primes with $p_{n}<p_{j}$ where the $n$ and $j$ denotes the $n$th and the $j$th prime. I have this sum $$\sum \limits^{k=\frac{b-p^{2}_{n}p_{j}}{2p_{n}p_{j}} ...
1
vote
1answer
55 views

Show that $\limsup_{x \to \infty} \frac{\pi(x)}{x/ \log x} \geqslant 1. $

Show that $$\displaystyle\limsup_{x \to \infty} \dfrac{\pi(x)}{x/ \log x} \geqslant 1. $$ I've seen $\displaystyle\lim_{x \to \infty}$ operator, but I haven't seen $\displaystyle\limsup_{x \to ...
1
vote
1answer
31 views

Euler's Totient function $\forall n\ge3$, if $(n-\phi(n)) = \sqrt{n}\ $,$\ $then $(n-\phi(n)) \in \Bbb P$

Recently I opened a question about what it might be a new property of Euler's Totient function. I am still studying the Totient function and I found another interesting relationship, it is very ...
3
votes
1answer
35 views

Product Divisors of 2 integers

If $x$ is a positive integer, and $y$ is a positive integer, can the product of the divisors of $x$ equal the product of the divisors of $y$ for some arbitrary $x$ and $y$? (the product of the ...
4
votes
3answers
60 views

Show that $\sum\limits_{p \leqslant x}1/p = \frac{\pi(x)}{x} + \int_2^x \frac{\pi(u)}{u^2} du.$

Show that $$\displaystyle\sum\limits_{p \leqslant x}1/p = \dfrac{\pi(x)}{x} + \int_2^x \dfrac{\pi(u)}{u^2} du.$$ In the equation above, $\pi(x)$ denotes the prime counting function. To get ...
0
votes
1answer
41 views

Number of solutions of the congruence $x^p \equiv x\pmod p$

How do I show that $x^p \equiv x\pmod p$ has precisely $p$ solutions? I can use Lagrange's theorem and Fermat's little theorem.
1
vote
0answers
18 views

Is there a standard notation for $(p_i-k)(p_{i-1}-k)(p_{i-2}-k)\cdots$ where $k$ is a small positive integer

For $k=0$, there is: $p_i\# = (p_i)(p_{i-1})(p_{i-2})\cdots(5)(3)(2)$ For $k=1$, there is: $\varphi(p_i\#) = (p_i-1)(p_{i-1}-1)(p_{i-2}-1)\cdots(5-1)(3-1)(2-1)$ Is there any other notation that ...
7
votes
0answers
129 views

Euler's Totient function $\forall n\ge3$, if $(\frac{\varphi(n)}{2}+1)\ \mid\ n\ $ then $\frac{\varphi(n)}{2}+1$ is prime

While I was studying Euler's Totient function, $\varphi(n)$, I stumbled upon the marvelous book "Index to Mathematical Problems, 1980-1984" By Stanley Rabinowitz. In this page of the book (link to ...
2
votes
0answers
159 views

Numbers $717, 71717, 7171717,\dots$ and primality

Prove or disprove that all numbers $717, 71717, 7171717,\dots$ are composite. This is related to this question. $\begin{array}\\ 717 &= \text{div by 3}\\ \color{blue}{71717} &= 29\cdot ...
6
votes
1answer
36 views

Are there infinitely many Smarandache-Wellin primes and does anyone care?

Definition: The $n$th Smarandache-Wellin number in base $m$, denoted $S_n^m$ (or just $S_n$ for $m=10$), is the concatenation of the first $n$ base-$m$ primes. So, for example, we would have $S_4 = ...
2
votes
2answers
42 views

Number Theory Primitive Roots Confusion

The following theorem is in my lecture notes: If p is a prime number, then there exist φ(p-1) distinct primitive roots modulo p. I am struggling to make sense of this. φ(m) is the number of ...
10
votes
1answer
205 views

Is this olympiad-like question about remainders an open problem?

Suppose that we are given two positive integers $x$ and $y$ such that $$x \mod p \leqslant y \mod p$$ for each prime number $p$. (Here, $x \mod p,\; y \mod p$ stand for the least non-negative ...
1
vote
3answers
190 views

Convergence of series involving the prime numbers

Given the serie $A=\sum\limits_{n=1}^{+\infty}\frac{p_n}{p_{n+1}}$ and $B=\sum\limits_{n=1}^{+\infty}\frac{p_{2n}}{p_{2n+1}}$, where $p_n$ is the sequence where the nth number are the nth prime ...
4
votes
1answer
102 views

Sequence with Prime Numbers

I was looking a question in a calculus book which used the following steps to show that following sequence has a limit (called Euler's constant $\gamma$): $$t_n = \sum_{i=1}^n\left(\frac{1}{n}\right) ...
3
votes
3answers
98 views

Find all prime numbers of the form $n^2 + 4n$

Question: Find all the prime numbers of the form $n^2 + 4n$. List of the primes of this form and prove these are all such primes. My Answer I'm not really good at this but I made an attempt. $$n^2 ...
0
votes
2answers
51 views

Prove or disprove: There exists a prime p > 3 such that p + 2 and p + 4 are also prime

I'm having a lot of difficulties with this proof. Can someone please solve it and explain to me what's going on at each step? Thank you!
0
votes
0answers
39 views

Prove $\frac{-5-\sqrt{5}}{2}$ is a quadratic residue when $p\equiv 1\pmod 5$ [closed]

The number $5$ is a quadratic residue modulo $p$ when $p\equiv\pm1\pmod 5$. How to prove that $\frac{-5-\sqrt{5}}{2}$ is a quadratic residue modulo $p$ when $p\equiv1\pmod5$, and ...
2
votes
5answers
60 views

Possible solutions of a diophantine equation: $p^2+pq+275p+10q=2008$

What are couples of prime integers that verify this diophantine equation: $$p^2+pq+275p+10q=2008?$$ I tried to solve this equation trough the rules of modular-arithmetic. I rewrite the equation as: ...
5
votes
1answer
202 views

Heuristic explanation for oscillatory behavior of first $n$ primes' multiples

Let $A$ be the set of all multiples of the first $n$ primes. The asymptotic density of $A$ should be given by $\mu=1-\prod_{i=1}^n(1-1/p_i)$. Letting $a_k$ be the $k$th element of $A$, the function ...
1
vote
1answer
43 views

Congruence mod $p$

I need a proof for the following: Suppose that $p$ is an odd prime. If $(a, p) = 1$, then $x^2 = a \pmod p$ either has exactly $2$ solutions or has no solutions within $\textrm{crs}/p$. I can come ...
1
vote
2answers
55 views

Polynomials mod prime $p$

The problem is $5m^2+m+4 \equiv 0\pmod 7$. I am supposed to first convert it to a quadratic whose first coefficient is $1$. But the polynomial cannot be factored, so I am unsure as to how to do ...
0
votes
1answer
56 views

Erdős Prime Sieve Conjecture

I think this is/was an Erdős conjecture. I can't find it, or see how to prove it. We know all primes but a finite number can be expressed as $6k\pm1$. If we have a finite set of moduli using ...
2
votes
2answers
69 views

Determine if $n$ is prime?

If $n < 10^6$ and no integer between $1$ and $10^4$ divides $n$. Is n prime? Here is my attempt: Assume $n$ is prime. Then using trial division, $n$ must be divisible by an integer between $1$ ...
2
votes
0answers
17 views

Solution to a set of number theoretic constraints

I'm trying to prove a graph theoretic lemma for my research; I need to construct graph homomorphisms between some delicately defined graphs. I believe I can do this if (and maybe only if) I can find ...
4
votes
1answer
46 views

Quadratic bound for prime numbers

I once found the following problem meant to be solved at high-school level (some olympiad-level exercise, I guess), and I have never been able to prove it using elementary methods. Does anybody know a ...
0
votes
1answer
25 views

Convergence behavior of $\sum_p \frac{1}{p \log p}$ and generalization.

The harmonic series $$\sum_{n\in\mathbb N} \frac{1}{n}$$ is well known to be divergent. Using Cauchy condensation test one immediately sees that even $$\sum_{n\in\mathbb N} \frac{1}{n\log n}$$ is ...
2
votes
2answers
41 views

If p and q are prime which elements are in the subgroup? (GRE question)

I was just doing some practice problems in my abstract algebra book trying to get a warm up this morning, but I found a GRE problem in the problem set and I don't know how to solve it. I've tried to ...
-4
votes
0answers
35 views

Number Theory questions [duplicate]

Let $a$ be an integer and $n$ a positive integer. Prove or provide a counter example to each of the following statements. (a) If $a$ ≡ ± 1(mod p) for all primes $p$ dividing $n$, then $a^2$ ≡ 1(mod ...
4
votes
1answer
111 views

Elementary proof for $\sqrt{p_{n+1}} \notin \mathbb{Q}(\sqrt{p_1}, \sqrt{p_2}, \ldots, \sqrt{p_n})$ where $p_i$ are different prime numbers.

Take $p_1, p_2, \ldots, p_n, p_{n+1}$ be $n+1$ prime numbers in $\mathbb{P} \subseteq \mathbb{N}$. $\sqrt{p_{n+1}} \notin \mathbb{Q}(\sqrt{p_1}, \sqrt{p_2}, \ldots, \sqrt{p_n})$ seems to be quite ...
1
vote
1answer
49 views

Is $p\in\big\{x,…,2x\big\}$ lower-bounding $p\in\big\{x^2,…,(x+1)^2\big\}$?

Is it overreaching or erroneous to consider that possibility? (Alas, I'm not a mathematician, and don't have rigorous language to talk about this.) What I want to say is: Given any even span of ...
0
votes
1answer
20 views

$\sum_{n=2}^{\infty}[\log{(\log{(p_{n+1})})} - \log{(\log{(p_n)})}] - \frac{1}{p_{n+1}} = C$?

With $p_n$ prime, does the constant, $C$, exist and have a name? $$\sum_{n=1}^{\infty}[\log{(\log{(p_{n+1})})} - \log{(\log{(p_n)})}] - \frac{1}{p_n} = C$$ If not,how about a constant and function ...
-3
votes
2answers
40 views

Proof of infinite primes

Recently , I was going through some Euclid's Lemma and I read Euclid's Proof for infinite Prime . When I read it , I found it amazing. But then thinking of How to prove it in other ways .I came to ...
7
votes
2answers
161 views

What percentage of numbers is divisible by the set of twin primes?

What percentage of numbers is divisible by the set of twin primes $\{3,5,7,11,13,17,19,29,31\dots\}$ as $N\rightarrow \infty?$ Clarification Taking the first twin prime and creating a set out of its ...