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

1
vote
2answers
38 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 ...
4
votes
1answer
125 views
+50

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 ...
3
votes
1answer
36 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 ...
-1
votes
0answers
27 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
0
votes
1answer
14 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
17 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
30 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
41 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
2answers
542 views

What is the first 21-digit prime number after the decimal point of Pi

We know the recent computers are 64-bit, and the maximum integer number is 18446744073709551615, whether you can find the first 21-digit prime number after the decimal point of $\pi$? Please show me.
1
vote
1answer
43 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
99 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 ...
8
votes
0answers
90 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{\...
4
votes
2answers
61 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\} $$ ...
6
votes
8answers
430 views

If a prime $p\mid ab$, then $p\mid a$ or $p\mid b$

If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an ...
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 ...
1
vote
1answer
38 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
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 ...
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?
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}...
6
votes
1answer
132 views

Prove or disprove that ${F_{n}^2} + 43$ is always a composite

This is a kind of follow-up to another question, but in order not to burden that question and its answers with new comments, I decided to create this separate question. Also, it looks this problem is ...
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 ...
2
votes
1answer
80 views

Are there infinitely many pairs of primes, $p$ and $q$, such that $q = 4p + 1$?

How close can one come to proving that there are infinitely many primes, $p$ and $q$, such that $q = 4p + 1$? The idea for this question came from reading the question and answers posed by user39898,...
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
109 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 ...
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 ...
70
votes
6answers
8k views
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 $...
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 "...
0
votes
2answers
60 views

If $b^2 \equiv 1 \pmod 3$, is it possible to have $\sigma(b^2) \equiv b^2 \pmod 3$?

The title says it all. Let $\sigma(N)$ denote the sum of the divisors of the positive integer $N$. To paraphrase my question: If $3 \mid \left(b^2 - 1\right)$, is it possible to have $3 \mid \...
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:...
3
votes
4answers
114 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$ ...
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
77 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?
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
40 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
47 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$, ...
9
votes
0answers
129 views

Are my calculations of a new constant similar to Mill's constant based on $\lfloor A^{2^{n}}\rfloor$ and Bertrand's postulate correct?

As Wikipedia explains in number theory, Mills' constant is defined as: "The smallest positive real number $A$ such that the floor function of the double exponential function $\lfloor A^{3^{n}}\...
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)=...