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
34 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 ...
1
vote
0answers
109 views

Conjecture: for even n without primitive roots modulo n, the set of $m \in Max(ord_n(k))$ contains one pair of primes $p_1+p_2=n$ (Goldbach)

Conjecture: for those n even numbers that do not have primitive roots modulo n ,$Pr(n)$, the set $M(n)$ of those $k$ having a maximum multiplicative order $ord_n(k)$ contains at least a pair of primes ...
4
votes
1answer
71 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, ...
2
votes
2answers
58 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 ...
1
vote
1answer
43 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 ...
0
votes
2answers
50 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] = {} & ...
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
35 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 ...
0
votes
0answers
55 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 ...
1
vote
1answer
41 views

A question on Primes in Arithmetic Progression

We know that an arithmetic progression has to have a composite number since there are arbitrarily large gaps between primes. But I was wondering whether the following construction is possible: Can ...
1
vote
0answers
28 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 ...
1
vote
0answers
67 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 ...
4
votes
1answer
109 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 ...
1
vote
2answers
37 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$ ...
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
55 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
67 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 ...
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 ...
0
votes
3answers
155 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, ...
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 ...
8
votes
1answer
88 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 ...
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, ...
1
vote
1answer
95 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 ...
5
votes
3answers
1k 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$?.
1
vote
1answer
36 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 ...
0
votes
2answers
497 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 ...
1
vote
1answer
70 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 ...
2
votes
2answers
39 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?
3
votes
3answers
99 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
2answers
32 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.
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
59 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
47 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 ...
0
votes
0answers
27 views

Reverse proof of Fermats Little Theorem [duplicate]

Let $n \in \mathbb{N}$. For all $x \in \{1,2,...n-1\}$ it is: $x^{n-1} \equiv 1 \text{ mod } n$. Show that $n$ is prime. This seems to be proving Fermat's little theorem the other way round. Until ...
0
votes
1answer
63 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)$ ...
0
votes
1answer
45 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 ...
3
votes
2answers
86 views

Backwards proof of Fermat's Little Theorem

$$\textrm{Let }p \in \mathbb{N}. \textrm{ Show that }\forall n \in \left \{ 1,2,...,p-1 \right \} \textrm{if } n^{p-1} \equiv 1 \mod p \Rightarrow p \in \mathbb{P}$$ This is basically Fermat's ...
10
votes
3answers
95 views

Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$.

So the problem states: Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$. I was thinking about trying to prove this using the corollary to ...
2
votes
0answers
54 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 $ ...
5
votes
6answers
631 views

Polynomial with a prime number as a root

Is it possible to prove that this equation is false: $$ \sum_{i=0}^n a_i p^i = 0 $$ with following conditions: $a_i \in [-1;1]$; [Might $a\in\{-1,1\}$ have been intended here?] $p$ is a prime ...
9
votes
2answers
235 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
1answer
65 views

Number $N>6$, such that $N-1$ and $N+1$ are primes and $N$ divides the sum of its divisors

The perfect number $6$ is in the middle of the primes $5$ and $7$. It is the only perfect number with this property because odd numbers are not in the middle of two twin primes and even perfect ...
1
vote
2answers
64 views

Where can I find a list of large prime numbers

A repository of say 13 digit prime, 15 digit primes etc.
3
votes
1answer
68 views

Bounds for $n$-th prime

In this page I have found that the bounds for $n$-th prime is given by, $$n(\ln n+\ln \ln n)>p_n>n(\ln n+\ln \ln n-1)$$ for all $n\ge6$. Are there even stronger bounds for the $n$-th prime? If ...
1
vote
1answer
56 views

Upper bound on the maximal number of prime factors

I would like to prove $$\omega(n) \le \frac{\ln{n}}{\ln\ln{n}}$$ This is a quite standard result, but I haven't been able to find a proof. Here's what I've tried doing: ...
5
votes
1answer
49 views

weakened version of Dirichlet's theorem - proof without Dirichlet's theorem

Dirichlet's theorem states that arithmetic sequence with first term and common difference relatively prime, contains infinitely many prime numbers. Assume that we only want infinitely many numbers in ...
7
votes
1answer
85 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 = ...
2
votes
1answer
23 views

Division of the Binomial Coefficient

Prove that when p is prime, the binomial coefficient p!/(r!)((p-r)!) is divisible by p with r being greater than or equal to 1 and less than or equal to p-1 . Clearly p! is divisible by p so I cant ...
1
vote
3answers
40 views

Prove there exists $m$ and $k$ such that $ n = mk^2$ where $m$ is not a multiple of the square of any prime.

For any positive integer $n$, prove that there exists integers $m$ and $k$ such that: $$n = mk^2 $$ where $m$ is not a multiple of the square of any prime. (For all primes $p$, $p^2$ does not divide ...
10
votes
1answer
78 views

Mind-boggling property of a prime

As you have already probably known, an Emirp is a prime whose reversal give a different prime i.e: 37 is an Emirp because 37 is prime and its reversal 73 is also a prime, 79 is also an Emirp. Now I ...