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
34 views

Characterization of primes $(6n+1, 6n-1)$ that are not twins

According to OEIS Sequence A002822(https://oeis.org/A002822), it states that $6n+1$ is a twin prime $iff$ $n$ is not of the form $6ab \pm a \pm b$. I was wondering if anyone had a proof for this. ...
4
votes
1answer
63 views

Proof of primes of the form $6n+1$

According to OEIS Sequence A002476 (https://oeis.org/A002476), it says that all primes of the form $6n+1$ can be written in the form: $x^2 - xy + 7y^2$ with $x$ and $y$ non-negative. I was wondering ...
10
votes
0answers
125 views

Finding $1/x^2 + 1/x^3 + 1/x^5 + \dots $

The following function came up in my work: $$ f(x)=\sum_{p\text{ prime}}\frac{1}{x^p}=\frac{1}{x^2}+\frac{1}{x^3}+\frac{1}{x^5}+\frac{1}{x^7}+\frac{1}{x^{11}}+\cdots. $$ Naturally, this converges for ...
8
votes
0answers
65 views

Number of primitive roots mod $p$ that are not primitive roots mod $p^2$

Consider the primitive roots of a prime $p$ in the range $1...p$ which are not primitive roots mod $p^2$. Let $n(p)$ be this number. While looking for an answer to this question, it seems that the ...
1
vote
0answers
37 views

Set of primetwins below 30

The Subset $C$ of the primes between 1 and 30, which have at least one primetwin (eg. 11,13). Would this be correct? $C=\{x\in \mathbb{N}\backslash\{1\} :(\nexists a\in \mathbb{N}\setminus\{1,x\}(a\...
1
vote
1answer
45 views

Asymptotics of $\sum\limits_{n/2 < p \leq n} \frac{1}{p}$

I'm reading a paper which asserts the following: $$\sum_{n/2 < p \leq n} \frac{1}{p} \sim \frac{\log 2}{\log n}$$ follows from prime number theorem, where the sum is taken over $p$ prime. What is ...
2
votes
1answer
49 views

Show that the cube roots of three distinct prime numbers cannot be three terms (not necessarily consecutive) of an arithmetic progression

I'm thinking we could do a contradiction, maybe showing that one of the primes is a composite number if they are in a sequence, but I'm not sure how to finish this up. I had this as a math problem in ...
1
vote
1answer
23 views

Generate Sieve of Eratosthenes without “sieve” (generate prime set in interval)

How do I generate a list of primes based on the Sieve of Eratosthenes? I mean by excluding the divisible numbers beforehand, which is tricky for large numbers. I am an number theory amateur, but was ...
3
votes
0answers
40 views

How to show that for $n$ sufficiently large, relative to $k$, $(n+1)(n+2) \ldots (n+k)$ is divisible by at least $k$ distinct primes

I would like to show that $\displaystyle \frac{(n+k)!}{n!}$ is divisible by at least $k$ distinct primes whenever $n$ is sufficiently large. We all know that it is divisible by $k!$ and hence by $\...
4
votes
1answer
23 views

Turing Decryption Example

I know this exact same question exists but I am still having problems in understanding it. The following is given in the text: The message m can be any integer in the set {0,1,2,…,p−1}; in par­...
0
votes
2answers
49 views

proving theorem about perfect powers

Im currently studying the journal entitled Perfect Powers with All Equal Digits but One theorem: For a fixed integer $l \geq 3$, there are only finitely many perfect $l$-th powers all whose digits ...
2
votes
2answers
76 views

Enumeration of primes

Given a prime number $p$, there is an associated number $n(p)$, giving its ranking in the sense that $n(2)=1$, $n(3)=2$, $n(5)=3$ etc. Is there a closed form expression for $n(p)$ in terms of $p$?
2
votes
3answers
58 views

The arithmetic function $\lambda(n)=(-1)^{a_1+\cdots +a_k}$

Define $\lambda(1)=1$, and if $n=p_1^{a_1}\cdots p_k^{a_k}$, define $$\lambda(n)=(-1)^{a_1+\cdots +a_k}$$ How can I see that $$\sum_{d\mid n}\lambda(d)=\begin{cases} 1 \,\,\text{ if $n$ is a square}\\...
1
vote
1answer
73 views

Conjecture concerning modular arithmetic

Below $0\notin\mathbb N$. I want a proof or a counter-example of the following (corrected) conjecture: Suppose $p$ is the smallest prime dividing $n\in\mathbb N$ and suppose $kn+ap=m!$, where $...
1
vote
0answers
57 views

The Porsche prime

A friend told me that the number starting with 911 followed by 911 zeros ending with 119 (that is $911\cdot 10^{914}+119$) is a prime number, the so-called Porsche prime. Maple indeed confirms that ...
0
votes
1answer
13 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
51 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 (...
8
votes
1answer
442 views

Conjecture about primes and the factorial: for all primes $p>5$, must there exist a prime $q<p$ such that $q\equiv m!\pmod p$ for some $2<m<p$?

Below $0\notin\mathbb N$. Further corrected conjecture: For all prime numbers $p>5$ there exist a prime number $q<p$ such that $q\equiv m!\!\pmod p$, $2<m<p$. or Given a prime ...
1
vote
2answers
55 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
30 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
42 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
17 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)...
1
vote
0answers
30 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
34 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) \...
2
votes
1answer
61 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^...
6
votes
0answers
196 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
115 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
68 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
44 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
46 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\} $$ ...
3
votes
1answer
46 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
27 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
47 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
112 views

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

Solve the equation $\phi(N)=98$ I have no idea how to do it. How to find all N?
4
votes
1answer
133 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
1answer
18 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
68 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
53 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
29 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
115 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
30 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
44 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
127 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
100 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$...
2
votes
0answers
60 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
103 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
95 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
108 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}\\ \...