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

7
votes
4answers
129 views

Understanding the trivial primality test

I'm reading an algorithms book and I came across a code example for a primality test. The problem is that I couldn't understand the condition for the for-loop: ...
3
votes
1answer
48 views

Find all odd positive integers $n$ greater than $1$ such that for any coprime divisors …

Find all odd positive integers $n$ greater than $1$ such that for any coprime divisors $a$ and $b$ of $n$, the number $a + b − 1$ is also a divisor of $n$. This was taken from the Russian ...
2
votes
1answer
33 views

Question on Furstenberg topology on Z and P subspace of primes

Hi all I was given this question: I have Z (the integers) with the Furstenberg topology on it, i.e. the topology induced by non constant arithmetical progressions presented here, and I am asked to ...
3
votes
2answers
32 views

Contradicting $p|n $s.t $p > \sqrt n$

I have proved a basic theorem in prime numbers, If $n \ge 2$ and $n$ is composite, then it is divisible by some prime $p \le \sqrt n$. This is a fairly basic result, and then my textbook shows me how ...
5
votes
0answers
73 views

A problem about $e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$

Let $\alpha_i\in [0,1),\; i\in \{1,\cdots,N\}$ for some positive integer $N$, such that $$e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$$ and if for any non-empty proper subset ...
1
vote
3answers
30 views

Basic question about modular arithmetic applied to the divisor sum function $\sigma(n)$ when $n=5p$

While studying the divisor sum function $\sigma(n)$ (as the sum of the divisors of a number) I observed that the following expression seems to be true always (1): $\forall\ n=5p, p\in\Bbb P,\ p\gt ...
2
votes
1answer
55 views

Most Common Difference Between Two Consecutive Primes?

The question is as stated in the title. I was given this interesting problem by a friend of mine, but I don't know how to proceed with a solution. The immediate thought I had was that the most common ...
1
vote
2answers
38 views

If $n \in \mathbb N$, under what conditions are $n$ and $n+2$ relatively prime?

The Statement of the Problem: If $n \in \mathbb N$, under what conditions are $n$ and $n+2$ relatively prime? My Thoughts: I know that the answer is that $n$ must be odd. However, I'm not sure how ...
3
votes
0answers
37 views

Are there any known special properties of a number located between twin primes?

With the exception of $4$, every number located between twin primes is divisible by $6$. This one is obvious, but are there any other properties that can be ascribed to such numbers? A property may ...
2
votes
2answers
83 views

A miraculous number N

Of course we can talk about 1 digit prime numbers, 2 digit primes , 3 digit primes , and so on..., my question is : is there an N (N greater than zero) such that there are no N-digit prime numbers ? I ...
2
votes
1answer
52 views

Using Fermats prime numbers to prove that there is infinitely many prime numbers

A Fermat number $F_n$ is of the form $F_n = 2^{2^n} + 1$ Furthermore, $F_n = 2 + F_0F_1F_2......F_{n-1}$ Now I already proved that if $n \neq m$ then $\gcd(F_n,F_m) = 1$ Here is the proof Without ...
4
votes
1answer
41 views

Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \le j \le n$

Let $p$ be a prime number and $a_1, a_2, \ldots, a_n$ be integers. Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \leq j \leq n$. The hint was to use induction. ...
2
votes
2answers
42 views

Suppose $p$ is a prime number and $a$ is an integer. Show that if $p \mid a^n$, then $p^n \mid a^n$ for any $n \geq 1$?

I know that if $p \mid a^n$, I can say $a^n = pr$ for some integer $r$, you can also conclude that $\gcd(p, a^n) = p$, but I'm not sure how to use that information if I even can to show that $p^n \mid ...
1
vote
0answers
57 views

Prove that if $3^\frac{F_n-1}{2} \equiv -1 \pmod {F_n}$, then $F_n$ is prime

$F_n = 2^{2^n} + 1$ is a Fermat Number. Here is my attempt. We square each side of the congruences we get $$3^{F_n-1} \equiv 1 \pmod {F_n}$$ Now I already know that whenever $m \neq n$ then $ ...
1
vote
2answers
35 views

Do groups of prime order have one subgroup?

So let's say that I have a group of order $p$, where p is prime; does that group only have one subgroup? I've look at the wiki article and it says there's a trivial and actual solution, so can we ...
0
votes
2answers
39 views
1
vote
0answers
48 views

the sum of the reciprocals of the primes

The sum of the reciprocals of the primes is $\sum \limits_{p}\frac{1}{p} \approx N \ln\ln(N)$ what about this sum where $p_{3}=3,p_{5}=5,p_{n}=\sum \limits^{N}_{j=5}\frac{1}{p_{j}} \sum ...
1
vote
0answers
73 views

Fermat's Little Theorem and prime divisors

Let $a,b\in\Bbb N$ and $a+b$ be an even number. Assume $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
58 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
26 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
27 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
23 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
37 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
28 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
36 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
99 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
26 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
37 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
33 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
38 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
1answer
67 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
51 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
24 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
35 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
19 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 ...
8
votes
0answers
154 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
173 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
231 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
192 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
108 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
99 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!