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

-6
votes
3answers
116 views

Is this the real reason why 1 is not prime? [duplicate]

Divisibility by 1 is misleading as it does not divide a number into smaller parts. If divisibility by 1 is disallowed, then: The Unit: A whole number that is indivisible. Prime: A whole number that ...
3
votes
1answer
49 views

Is this reasoning correct for average prime gap?

Since \begin{align} &\operatorname{li}(n)\sim\Pi (n)\equiv\sum _{k=1}^{\lfloor \log (n)\rfloor } \frac{\pi \left(n^{1/k}\right)}{k}\\ \end{align} then the average gap for \begin{align} ...
0
votes
0answers
52 views

Looking for a function which can serve as an upper bound to a count of the the pairs (x)(x+2) that have a given least prime factor?

Let $p \ge 7$ be a prime. Let $z > p$ also be a prime. Let $f_p(z)$ be the number of elements $x$ such that $z \le x < z^2$ and the least prime factor of $x(x+2) = p$ I am trying to find ...
0
votes
0answers
46 views

Solve an equation of the prime counting function

The problem is, Find all the positive integral values of $x$ for which we have, $$\pi(p_n-x)=\pi(p_{n+1}-x-1)$$where $\pi(x)$ denotes the number of primes not exceeding $x$. I don't know where ...
0
votes
1answer
30 views

Notation about factors

What is the name (if there is one) of the "full factorization representation" of a number, in which also the powers of the factors are (recursively) decomposed until all the numbers used in the ...
0
votes
4answers
1k views

Co Prime Numbers less than N

I need to find all the numbers that are coprime to a given $N$ and less than $N$. Note that $N$ can be as large as $10^9.$ For example, numbers coprime to $5$ are $1,2,3,4$. I want an efficient ...
2
votes
2answers
51 views

prime number problem:

How can I show that; For any prime $p,$ there exist $u, v\in\mathbb{N}\setminus{\{p\}}$ ( and depend on $p$) such that $\color{Purple}{p\mid uv}$ and both ...
0
votes
2answers
49 views

Let $p$ be a prime. Prove that $\sum_{i=0}^{p}\binom pix^i \equiv x + 1 \pmod p$

Let $p$ be a prime. Prove that $\displaystyle\sum_{i=0}^{p}\binom pix^i \equiv x + 1 \pmod p$. i got \begin{align} & \frac{p!}{i!(p-i)!}(x^0+x^1+x^2+x^3+x^4+\cdots+x^p) \\[4pt] = {} & ...
4
votes
1answer
70 views

A consequence of the inequality $\pi(x)+\pi(y)\ge\pi(x+y)$

Assume that the inequality $\pi(x)+\pi(y)\ge\pi(x+y)$ holds for all integers $x,y>2$ where $\pi(x)$ denotes the number of primes less than or equal to $x$. Then find all $m$ and $n$ such that, ...
1
vote
1answer
36 views

Is this bullet really needed in Furstenberg's proof of infinitude of primes?

See here . The bullet I'm referring to is: Any union of open sets is open: for any collection of open sets $U_i$ and $x$ in their union $U$, any of the numbers $a_i$ for which $S(a_i, x) \subset ...
2
votes
1answer
75 views

$\prod_{ p\leq x}p\leq 4^{x-1}$ for all real $x\geq2$

How you prove this? I'm looking the Erdös proof from Bertrand Postulate and there are many things I don't get. Please don't hints, I'm newbie in combinatorics techniques. In the book I don't get ...
3
votes
1answer
96 views

Conjecture about the product of the primitive roots modulo a prime number ($\prod Pr_p$)

While I was learning about the primitive roots modulo $p \in \Bbb P$ (I will call $Pr_p$ to the complete list of the primitive roots module $p$) and having in mind the conjecture explained in this ...
2
votes
0answers
37 views

How many entries in the sequence $x_n$ given by recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ are known?

The sequence $x_n$ with the recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ , where $p_k$ denotes the $k-th$ prime, has the following values : ...
0
votes
1answer
32 views

Diffie Hellman: Subgroup Confinement Attack

how can I solve the following tasks? a) Find all primitive elements of $\mathbb{Z}_{37}$. I guess the only possibility here is to try if the remainder off all elements from 1 to 36 to the power ...
1
vote
0answers
61 views

Problem with multivaluedness of $(-1)^{\frac 14}$

Assume that $p\equiv3\mod4$ is an odd prime and $k$ an odd number. Then $$m=(-1)^{\frac{p^k-p^{k-1}+2}{4}}$$ seems to be always the value $1$ (?). This would be interesting how one can prove this - I ...
1
vote
0answers
26 views

Estimating the number of elements with a given least prime factor in a sequence of consecutive integers

Let $a,n$ be any positive integers. Let $\varphi(x)$ be the Euler totient function. It seems to me that the number of elements $x$ with $a \le x < a+n$ that have a given least prime factor will ...
3
votes
1answer
136 views

Is there a way to relate prime numbers and the fourier transform

According to what I know about Fourier transforms, any continuous periodic signal can be represented as a combination of sine and cosine functions. To me, this looks analogous to the "Fundamental ...
-1
votes
1answer
151 views

Integer linear combinations of coprime integers

Consider the finite set $S=\{s_1,s_2,\dots,s_n\}$ such that $GCF(s_1,s_2,\dots,s_n)=1$. Show that $\exists n$ such that $n$ cannot be written as $n=c_1s_1+c_2s_2+\dots+c_ns_n \forall c_i,s_i \in ...
1
vote
2answers
33 views

A question on perfect square

Prove that if $ab$ is a perfect square and $\gcd(a,b)=1$, then both $a$ and $b$ must be perfect squares. Their Answer: Consider the prime factorization $ab=p_1^{e_1}\cdots p_k^{e_k}$. If $ab$ ...
0
votes
2answers
79 views

Fermat little theorem : show that if $p$ is prime, then $a^p \equiv a\pmod p$ holds, if $p$ divides $a$.

Fermat little theorem : show that if $p$ is prime, then $a^p \equiv a \pmod p$ holds,if $p$ divides $a$. I know it doesn't hold but I'm having a hard time proving it.. I know that if $p$ divides ...
0
votes
3answers
153 views

Proving prime number combinatorics

I am trying to figure out the following review problem: Let $p$ be a prime number and $a$ be a natural number. Prove that the following (parts 1, 2, 3 and 4) are true for every $p$ and $a$. Here, ...
4
votes
2answers
32 views

Property of the sequence of primes

Let $p_n$ denote the $n$-th prime number. Does anyone know a proof of the following property? $$\forall n, n', \ p_n p_{n'} \geq p_{n+n'}$$ I'm surprised I can't find anything on this while I ...
5
votes
3answers
52 views

$a^{13} \equiv a \bmod N$ - proof of maximum $N$

From Fermat's Little Theorem, we know that $a^{13} \equiv a \bmod 13$. Of course $a^{13} \equiv a \bmod p$ is also true for prime $p$ whenever $\phi(p) \mid 12$ - for example, $a^{13} = a^7\cdot a^6 ...
3
votes
1answer
64 views

The number of primes in an interval

What is the smallest known $c$ so that for any $n\geq 2$ there are at least $n/\log_2{n}$ primes between $n$ and $cn$ (inclusive)? The prime number theorem seems to give an asymptotic result so I am ...
1
vote
1answer
92 views

What is the next prime number?

Given an integer \begin{equation*} N~\text{such that}~N\leq 10^{18}, \end{equation*} what is the next prime number after this number? What approach should I use to solve this problem? (Problem ...
9
votes
2answers
225 views

Yet another conjecture about primes

Let $\mathcal{N}(n)$ be the next prime greater than $n$. Conjecture: $\mathcal{N}(n!)-n!\:$ is either $1$ or a prime. It holds for n=1 to 99 and the expression is 1 for 3,11,27,37,41,73,77 and ...
2
votes
0answers
29 views

If $q$ is a prime, $gcd(x(x+2),q\#)=1$ and $q < x < q^2$, doesn't it follow that $x,x+2$ are twin primes?

I recently asked a question that was not well received. That's ok. I don't disagree with the ratings if my question is unclear. I want to verify the foundation of my reasoning. Doesn't it follow ...
2
votes
3answers
350 views

About linear combinations of primes

$a,b,c$ are natural numbers whose greatest common divisor is $1$. $a,b,c\in\mathbb{N}^*$, $(a,b,c)=1$ Try to write down the expression using $a,b,c$ of the biggest natural number $M$ that cannot be ...
1
vote
0answers
54 views

What are the next few “tetranacci-like” pseudoprimes?

Starting with $n=0$: $k=2$ Given the roots $x_i$ of $x^2-x-1=0$. Then, we have the Lucas numbers, $$A_n = x_1^n+x_2^n = 2, 1, 3, 4, 7, 11, 18,\dots$$ The $n$ that divides $A_n-1$ are all the ...
8
votes
1answer
83 views

How to find this number, which is probably a very big prime or a product of big primes?

Let $\mathcal{N}(n)$ be the next prime greater than $n$. Which is the smallest natural number $n>0\;$ such that: $\mathcal N(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot n)−2\cdot 3\cdot 5\cdot 7\cdot ...
5
votes
2answers
36 views

A question about the proof that for prime p, p divides k(p), where k() is the Perrin sequence

Define the Perrin sequence by $k(1)=0$, $k(2)=2$, $k(3)=3$, and $k(n)=k(n-2)+k(n-3)$. We find that mostly $n$ divides $k(n)$ iff $n$ is prime, although there are a few exceptions called "Perrin ...
9
votes
2answers
692 views

Can insight be derived from direct formulae for prime number functions?

I was attempting to construct a formula for the n th prime using elementary functions - I didn't achieve this* but I did come up with some formulae in finite products and sums of elementary functions ...
0
votes
2answers
482 views

How to determine if a number $A$ is divisible by all the prime factors of $B$?

How to determine if a number $A$ is divisible by all the prime factors of $B$? For example: $120,75$ $A=120=2^3\times3\times5$ and $B=75=3\times5^2$ Therefore yes, $A$ is divisible by the prime ...
3
votes
1answer
40 views

$n^{q}\equiv1~(\text{mod $p$})$ is possible solve this? [closed]

I have the following situation: Let $p, q$ be a prime numbers were $p>q$ and $n\in\{0,1, \ldots, p-1\}$. In this conditions is possible solve (in function of $n$) this equation, ...
5
votes
3answers
922 views

One number divisible by all prime factors of another?

Given two numbers $x$ and $y$, how to check whether $x$ is divisible by all prime factors of $y$ or not?, is there a way to do this without factoring $y$?.
2
votes
2answers
38 views

PNT for composites

Is it true that \begin{align} &c_n\sim n+\operatorname{li}(n)+\operatorname{li}(n)/\log (n),\\ \end{align} where $c_n$ is the $n$th composite number? Is a better estimate known?
9
votes
5answers
4k views
0
votes
1answer
33 views

$\limsup_{n\to\infty}\frac{g_n}{\log^3 p_n} < \infty$?

The following quote comes from Wikipedia http://en.wikipedia.org/wiki/Prime_gap "Usually the ratio of $g_n / \log p_n$ is called the ''merit'' of the gap $g_n$;. In 1931, E. Westzynthius proved that ...
1
vote
2answers
89 views

Understanding a proof showing that for any prime $p$, there are integers $x$ and $y$ such that $p|(x^2+y^2+1)$.

I asked this question a couple days ago: Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $. But I asked it as a guest, and I could not comment on ...
1
vote
0answers
95 views

parity of powers of prime factors

lets consider the prime factorisation of a number N let the powers of the primes in this factorisation be a,b,c ....and so on. Is there a way to determine whether the number of powers that are even ...
1
vote
1answer
32 views

Number of possible solutions in modular equation

I have given the result value $z$. I know that $$z \equiv x\cdot(x-1)\pmod p$$ where $p$ is prime and the value $p$ is fixed and given. I have also given the information, that $x \in \{m, M\}$, where ...
7
votes
1answer
82 views

Carmichael numbers of form $m^3+1$ and Ramanujan's $1729$

While researching for a post on tetranacci pseudoprimes I came across a list of Carmichael numbers, $$C_n = 561,\, 1105,\, 1729,\, 2465,\, 2821,\dots$$ Of course, Ramanujan's taxicab number $1729 = ...
1
vote
1answer
64 views

The following is a necessary condition for a number to be prime, from its digit expansion. Has it been referred somewhere?

Concerning a numbers’ digits we know some necessary conditions on them for the number to be prime, besides the last digit having to be odd (except for prime 2). For example in decimal representation ...
0
votes
1answer
61 views

Are these two definitions of prime numbers equal?

In Coq for instance, prime numbers are defined ${n\ is\ prime} \doteq \forall a\in \mathbb{N}: a|n \rightarrow (a=1 \vee a=n)$ ...
2
votes
0answers
50 views

A multivalued function $ f(x) = 0 $ with integer solutions $ x_1=p(n) $ and $x_2=q(n) $

Please help me to define a multivalued function $ f(x) = 0 $ with integer solutions : $ x_1 = p(n)$ and $ x_2 = q(n) $ such that $\dfrac{ p(n) + q(n) } { 2 } = 2 n + 1 $ and $ ...
2
votes
2answers
30 views

Finding big exponential value

How to find the following most efficiently $$ A^{x} \bmod M $$ where $A,x\le10^{10}$ and $M$ is a quite big prime number.
3
votes
3answers
90 views

For a prime $p\ge 17$ is $\dfrac{p^2-1}{24}$ ever a prime?

It was indicated in the comments of this MO question that if $p\ge5$ is a prime then $24|p^2-1$. Indeed $p=6k\pm1$ and $p^2-1=36k^2\pm12k+1-1=12k(3k\pm1)$ and exactly one of $k$ and $3k\pm1$ is even. ...
2
votes
0answers
39 views

Prove an inequality of composite numbers

Yesterday after reading this post I tried to prove the inequality as given in the post. The inequality is, $$c_m+c_n>c_{m+n}$$ for all $m,n\ge1$. The problem was regarding the following special ...
2
votes
3answers
55 views

Why is it that if you square two prime numbers and add them, you get a number that is even and is not a perfect square?

If you do $x^2 + y^2 = n$ where $x$ and $y$ are both prime numbers and are both greater than $3$, why is $n$ always an even number that isn't a perfect square?
3
votes
1answer
45 views

Could all iterates of $s(n)=2n+1$ be composite for some starting $n$?

Let $s(n)=2n+1$ and $\sigma(n)=\{n,s(n),s^2(n),s^3(n),\ldots\}$, where $s^3$ denotes functions composition, $s^3(n)=s(s(s(n)))$. For example $\sigma(11)=\{11,23,47,95,\ldots\}$. As another example ...