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.

learn more… | top users | synonyms

0
votes
1answer
11 views

Existence of a Repeating Divisor

I have $n$ integers $a_1, a_2, a_3, .., a_n$ let $X = a_1*a_2*a_3*...*a_n$. I want to know a single integer $F$ such that $F^2$ divides $X$. It is told that there will be atleast one such $X$ and ...
1
vote
1answer
29 views

Why is it not known if Mill's constant is rational or irrational?

The following text appears in the Mill's constant definition at the Wikipedia: There is no closed-form formula known for Mills' constant, and it is not even known whether this number is rational (...
1
vote
1answer
73 views

Conjecture about primes and the factorial

Conjecture: Given a prime $p>5$ there exist a prime $q<p$ such that $kp+q=m!$, for some $k,m\in\mathbb Z_+$ where $m>2$. I want help to prove the conjecture or to find a counter-...
1
vote
2answers
46 views

The eventual advantage of a primality test without known exceptions

The primality test of Fermat with base $2$ seems to be as secure as the computer hardware for testing numbers big enough. However, I think there are an infinite numbers of false primes using this ...
0
votes
0answers
28 views

Describe the prime elements of the ring $\mathbb Z[\sqrt{-2}]$ [duplicate]

I have a ring $\mathbb Z[\sqrt{-2}]$ and I need to describe all the prime numbers of that ring. How I can do that? Thank you
3
votes
1answer
37 views

Proving a number is Carmichael

here is my question: Let $p>3$ be prime, s.t $q = 2p-1$ and $g = 3p-2$ are primes as well. (For example $p=19$,$13$,$7$). Prove that $N = pqg$ satisfies $p-1|N-1$, $q-1|N-1$ and $g-1|N-1$. I ...
0
votes
1answer
16 views

A primality test using the gcd

Let $f:\mathbb{N} \rightarrow \mathbb{N}$ be defined by $$f(n) = gcd(n,\lfloor \sqrt{n}\rfloor ! \mod n).$$ Show that a) If $p$ is a prime divisor of $n$ with $p \leq \sqrt{n}$, then $p \mid f(n)...
0
votes
0answers
20 views

The asymptotic behaviour of $\sum_{1\leq k\leq N-1}\int_{p_k}^{p_{k+1}}\log x d[x]$, where $p_n$ is the nth prime number

Let $p_k$ is the kth prime number and consider for $N\geq 2$ the arithmetic function $$f(N)=\sum_{k=1}^{N-1}\int_{p_k}^{p_{k+1}}\log(x) d[x]$$ where $[x]$ is the integer part function (provide us in ...
1
vote
1answer
31 views

Question about distribution of primes

The following is from "Introduction to Number Theory" by Hardy and Wright. The book first states the following theorem Theorem A: If $\pi(x)$ is number of primes not exceeding $x$ then $\pi(x) \...
1
vote
1answer
45 views

What is the largest prime $p$ such that the decimal expansion of $1/p$ repeats with period 2017?

By this discussion on John Baez's Google+ feed, the primes $p$ such that the decimal expansion of $1/p$ repeats with period 2017 are exactly those primes which occur in the prime decomposition of $10^...
5
votes
0answers
54 views

Prime Powers and Differences of Consecutive Cubes

I am wondering if it has been proven that there does not exist a prime $p$ and an integer $r \ge 3$ such that $p^r = (n + 1)^3 - n^3$ for some integer $n$. Note that this is a special case of Beal's ...
5
votes
1answer
101 views

Is there a prime of the form $11^k+k^{11}\ $?

Is there a natural number $k\ge 1$, such that $11^k+k^{11}$ is prime ? I checked the numbers upto $k=3000$ and did not find a prime number. On the other hand, for $k=76$ and for $k=142$, there is no ...
4
votes
2answers
62 views

Notation for “the highest power of $p$ that divides $n$”

If $p$ is a prime and $n$ an integer, is there a standard or commonly used notation for "the highest power of $p$ that divides $n$"? It's a concept that is often used repeatedly in number-theoretic ...
3
votes
0answers
36 views

Is there an identity related to $\binom{n-j-1}{k}+\binom{k+j}{k}\pmod{n}$?

I noticed that when $n$ is an odd prime, the following congruence $$\binom{n-j-1}{k}+\binom{k+j}{k} \equiv 0 \pmod{n}$$ holds for $0 \le j \le \frac{(n-k)}2$ and odd values of $k$ such that $0 < k ...
2
votes
2answers
44 views

Computing a double integral with applications to prime numbers

I was reading the preprint [1] which contains on p. 7 the following formula (for $4<s\le6$): $$ f_1(s)=\frac{2e^\gamma}{s}\left\{\log(s-1)+\int_4^s\int_3^t\frac{\log(u-2)}{u-1}du\,dt \right\} $$ ...
1
vote
1answer
39 views

Uncertainty in a theorem about Sarrus numbers

From https://oeis.org/A001567 there is a theorem of Ray Chandler formulated: An odd composite number $2n + 1$ is in the sequence if and only if multiplicative order of $2\;(\text{mod}(2n+1))$ ...
1
vote
0answers
26 views

Function check-up exercise

I want to make sure I did everything correctly, so here's the exercise: Given $P$ the set of positive prime numbers and be $S = \mathbb N^* - \{1\}$. $\forall n \in S,\ \pi(n)$ is the set of the ...
1
vote
1answer
45 views

What are the different ways to get a first-order formula that express the statement“$P$ is the $n$-th prime”

I know that such a $2$-predicate formula exists since Enderton's have already constructed such a formula in his text on mathematical logic but it was not easy to remember so I wonder if there is other ...
0
votes
3answers
101 views

Find all N in $\phi(N)=98$ [on hold]

Solve the equation $\phi(N)=98$ I have no idea how to do it. How to find all N?
4
votes
1answer
131 views

Is the Fermat primality test secure enough for very big numbers?

The random variable $X_m$ is the number of trials before $n\notin\mathbb P\wedge n|2^{n-1}-1$ where $n$ is an odd random integer $2^{m-1} < n < 2^m$. Computer simulations makes me believe ...
1
vote
2answers
201 views

Is there a reason for the existence of prime numbers? [on hold]

Is there a reason for the existence of prime numbers, or is there a reason that some numbers are prime numbers, but others are not? Does the number theory have any answers or at least ideas about ...
1
vote
1answer
17 views

Function exercise check-up

I want to make sure I did everything correctly, so here's the exercise: Given $P$ the set of positive prime numbers and be $S = \mathbb N^* - \{1\}$. $\forall n \in S,\ \pi(n)$ is the set of the ...
1
vote
2answers
63 views

Legendre symbol $(-21/p)$

I am a bit confused with the question: For what prime $p$, $\left(\frac{-21}{p}\right) = 1$? I did something like that: $$\left(\frac{-21}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}...
1
vote
1answer
50 views

Primes is in P, proof of hendrik Lenstra Jr. lemma

In the paper describing AKS primality test : http://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf On page no. 8 Lemma 4.7 last paragraph, I cannot understand how number of ...
1
vote
1answer
28 views

Is the sum of coefficients 2?

Is the sum of the coefficients of the polynomial interpolation of the data $(1,p_1),(2,p_2),...,(n,p_n)$ for some positive integer $n$ (where $p_n$ is the $n$th prime) always equal to two? I've ...
7
votes
1answer
110 views

A question about arithmetic progressions and prime numbers

I took number $3$ and observed: $3$ is an arithmetic progression of length one. $3,5$ is an arithmetic progression of length two. $3,5,7$ is an arithmetic progression of length three. Then I took ...
0
votes
1answer
25 views

What is meant by strictly in this statement?

If $n$ is prime, then $n$ is not divisible by any prime number between 1 and $\sqrt{n}$ strictly. (Assume that $n$ is a fixed integer that is greater than 1.). I searched online and found that "...
1
vote
1answer
43 views

How to check if a number is prime? [closed]

I am having a problem with those numbers: 1) $2015^7 - 1$ 2) $817^2 + 53^2$. Especially when number is raised to a given power. My solution for the second point: $817^2$ is the same as checking $...
3
votes
4answers
116 views

How to calculate $9^{47^{51}} \mod 67$?

I've looked at some other related things on here, but this seems a little more complicated with the double exponentiation. Is there a general algorithm to calculate $a^{c_1^{c_2^{...^{c_n}}}} \mod p$ ...
5
votes
1answer
94 views

There are at least two solutions such that $2p_n=p_a+p_b$ ($p$ being prime)

I've stumbled across this playing around and summing primes at random during a boring lecture. Is this a known conjecture? Can it be proven? My conjecture: There exists at least one non trivial ...
3
votes
2answers
53 views

If $q(X)$ is reducible in $\mathbb Z[X]$, then it's reducible in $\mathbb Z_p[X]$ for every prime $p$

My book states, without a proof, that If $q(X)$ is reducible in $\mathbb Z[X]$, then it's reducible in $\mathbb Z_p[X]$ for every prime $p$. The contrapositive of the above result is more useful:...
0
votes
1answer
27 views

Is there anything known in general about upper and lower bounds for $\prod_{i\leq n\vee p_n>k}(p_i-k)$

I have no specific reason to ask this question other than seeing that it comes up quite often when I'm playing around with prime numbers. Let $$f(n,k)=\prod_{i \leq n\vee p_n>k}(p_i-k)$$ Where $p_i$...
7
votes
1answer
104 views

Why can't negative numbers be prime? [duplicate]

I was in a lecture on primes, when it occurred to me what negative numbers are excluded. Why exactly?
2
votes
0answers
59 views

Prime elements of ring $\mathbb{Z}[\sqrt{-21}]$ [closed]

Find prime elements of the ring $\mathbb{Z}[\sqrt {-21}]$. Please help with some ideas.
5
votes
3answers
78 views

Sum of three consecutive prime numbers is $173$

If I tell you that the sum of three consecutive prime numbers is $173$, how quickly could we find the biggest of these numbers?
8
votes
0answers
91 views

Generalizing the growth of sums of two squares

Consider the set $S$ of numbers which are the sum of two (integer) squares, and define $S(n)$ as the number of members of $S$ in $\{1,2,\ldots,n\}.$ It is well-known that $$ S(n) \sim \frac{Kn}{\sqrt{\...
6
votes
1answer
88 views

Restricted equality involving prime numbers

Given three real numbers such that $a + b + c = 0$, it can be proved that \begin{align*} \frac{a^{5} + b^{5} + c^{5}}{5} & = \frac{a^{3} + b^{3} + c^{3}}{3}\cdot \frac{a^{2} + b^{2} + c^{2}}{2}\\ \...
1
vote
1answer
49 views

Why does this method for finding the number of factors for number X not work?

As you may know, in order to find the number of factors for natural number X, we take the prime factorization, add one to each exponent, and multiply, as such. $...
1
vote
0answers
41 views

A question about distribution of prime numbers

For prime numbers $p$, let $f(p) = \min\{k: p+k \text{ is prime}\}$. (BTW, is there a standard notation for this function?) For $p=113$ we have $f(p) = f(113) = 14$, i.e. the next prime number above ...
6
votes
0answers
51 views

A rash guess about distribution of primes based on meager empirical evidence?

Between the prime numbers $n=1327$ and $n+k = 1327+34 = 1361$ there are $k-1=33$ consecutive composite numbers. If you double those bounding primes, getting $2\times1327=2654$ and $2\times1361=2722$, ...
2
votes
3answers
103 views

A Formula For Primes

Could someone explain me why this arithmetic of sets can not be called a Prime Numbers formula? Was it already found before and is not relevant? Prime numbers sequence $\mathbb P$ (or set of members ...
1
vote
2answers
30 views

Show that $\mathcal{S}$ is a subbasis on $\mathbb{N}$

I was given a problem: (Edited) Show $$ S=\bigl\{S_p:p\in\mathbb{P}\bigr\}\cup\bigl\{\{1\}\bigr\} $$ where $\mathbb{P}$ is the set of prime numbers, and $S = \{n \in \mathbb{N}: n \text{ is a ...
0
votes
0answers
29 views

Probability distribution of $\omega'(n)$. [duplicate]

$\omega(n)$ is the number of distinct prime factors of $n$ and $\omega'(n)$ is the number of distinct prime factors of $n$ with multiplicity. For example if $p,q$ are prime numbers then $\omega(p^2q)=...
2
votes
2answers
173 views

Does there exist prime number of the form $0^0+1^1+2^2+3^3+4^4+…$ after the trivial one $2$?

I am interested with prime numbers of the form $0^0+1^1+2^2+3^3+4^4+....(n-1)^{n-1}+ n^n$ (where we take $0^0=1$). I've checked $n$ up to $250$, and I found that numbers of such form are very very ...
2
votes
0answers
44 views

Usefulness of largest known prime [duplicate]

Does it make sense to keep track of largest known prime? In other words: Are there any (more or less practical) situations, where we need the largest known prime? (except of the "situation" of ...
-1
votes
0answers
28 views

Function which gives number of primes STRICTLY less than a number x.

We all know that the $\pi(x)$ function (Prime-counting function) gives us the number of primes less than or equal to x. I'm interested in the function which specifically gives the number of primes ...
4
votes
0answers
50 views

Do DSm(n) never be a prime?

Smarandache number (denoted as Sm(n)), is a number formed from concatenating the first n natural numbers. For example Sm(11)= $1234567891011$ (http://mathworld.wolfram.com/SmarandacheNumber.html). And ...