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

2
votes
0answers
56 views

Prove $\left(\frac{q(q+1)}{p}\right) =\left(\frac{1+q^{-1}}{p}\right )$ for $p\gt2$ a prime, and any $q \in \mathbb{Z^+} $.

For $p\gt2$ a prime, and any $q \in \mathbb{Z^+} $, Show that $\left(\frac{q(q+1)}{p}\right) =\left(\frac{1+q^{-1}}{p}\right )$ where the terms are legendre terms. I saw this result as part of a ...
2
votes
0answers
137 views

For which positive integers n does there exist a prime whose digits sum to n?

Motivated by this earlier question, I thought of this problem: Question: For which positive integers $n$ does there exist a prime whose decimal digits sum to $n$? We can make two "easy" ...
2
votes
0answers
71 views

$\sum_p z^p$ where $p$ is prime

I've started reading Shakarchi's Complex Analysis, and I thought about something interesting. If I haven't mistaken, for any subsequence $A\subset \mathbb{Z}^+$, $\sum_{n\in A} z^n$ has radius of ...
2
votes
0answers
96 views

Searching for prime candidates

For some additional excitement, I've been searching for primes $p \gg q = 104729$, where $q$ is of course the ten-thousandth prime. It seems that the best way to search for prime candidates $p$ is to ...
2
votes
0answers
181 views

How many co-primes are there for a big integer N over a specified interval?

How many co-primes are there for a big integer $N$ over a specified interval ? bounds of $N$ are $[1,10^9]$ and the interval is $[a,b]$ where ($1\leq a\leq b \leq 10 ^{15}$) and there are $100$ ...
2
votes
0answers
33 views

Solving $key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$ with High limits

I was solving this equation:- $$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$ Given $$ 1,000,000,000 < a, n, m \; < 5,000,000,000 $$ $$ a, m \; are \;coprime $$ I solved it bruteforcely but it ...
2
votes
0answers
82 views

asymtotic ratio of nonsquarefree repunits

Let $R_n:=\frac{10^n-1}{10-1}$ (called a repunit) and $\mu$ be the Moebius function. Also $[n]:=\{1,2,3,\cdots, n\}, A_n:=\{m \in [n]| \mu (R_m)=0\}.$ What is the value of $\lim \limits_{n ...
2
votes
0answers
208 views

Integral with Sums of Prime Counting Functions

I came across the following integral, while working with products of $\zeta$ primes function: $$ \int_{1}^{x}t^{-s-1} \sum_{i=1}^{\pi(t^{1/2})}\left[\pi\left(\frac{t}{p_i}\right)-i+1\right] dt, $$ ...
2
votes
0answers
33 views

What is a good tool for this job involving the prime spiral?

I'm interested in studying the prime spiral interactively. This question talks about some interesting patterns in the spiral involving quadratic equations. The idea I had was, write a program that ...
2
votes
0answers
74 views

Prime numbers of the form: $k\cdot 2^n \pm 1$ , where $k<3n$

Is it true that : For every $n$ there exists a number $k<3n$ such that: $k\cdot 2^n-1$ or $k\cdot 2^n+1$ is prime,where $k,n\in \mathbf{N}$ Maple code that prints least $k$ such that ...
2
votes
0answers
68 views

Prime numbers of the form : $2^{n+a}+2^{n} \pm 1$ , where $0 \leq a < n$ and $n \equiv 0 \pmod 6$

Is it true that : For any positive integer $n$ such that $n \equiv 0 \pmod 6$ there is at least one prime number of the form: $p=2^{n+a}+2^{n} + 1$ , or , $p=2^{n+a}+2^{n} - 1$ with ...
2
votes
0answers
167 views

$n$ by $n$ Primally Magic Squares

(Again copied verbatim from a September 2009 thread I made.) A Primally Magic Square (PMS) is exactly like a traditional magic square with a change of criteria. Where a traditional magic square is ...
1
vote
0answers
57 views

Prove that if $3^\frac{F_n-1}{2} \equiv -1 \pmod {F_n}$, then $F_n$ is prime

$F_n = 2^{2^n} + 1$ is a Fermat Number. Here is my attempt. We square each side of the congruences we get $$3^{F_n-1} \equiv 1 \pmod {F_n}$$ Now I already know that whenever $m \neq n$ then $ ...
1
vote
0answers
48 views

the sum of the reciprocals of the primes

The sum of the reciprocals of the primes is $\sum \limits_{p}\frac{1}{p} \approx N \ln\ln(N)$ what about this sum where $p_{3}=3,p_{5}=5,p_{n}=\sum \limits^{N}_{j=5}\frac{1}{p_{j}} \sum ...
1
vote
0answers
73 views

Fermat's Little Theorem and prime divisors

Let $a,b\in\Bbb N$ and $a+b$ be an even number. Assume $a^2 - b^2 - a$ is an exact square, say $c^2$. Let $m = \frac {a+b}2$ and $n = \frac {a-b}2$. Then, $$(4m-1)(4n-1) = 4(4mn-m-n) + 1 = ...
1
vote
0answers
33 views

Marking Integers Using a Wheel

Suppose I had a wheel of diameter one meter and I was charged with marking every meter along an infinite stretch of a beach. The strategy is to insert pegs into the wheel so that every point that is a ...
1
vote
0answers
19 views

Is there a standard notation for $(p_i-k)(p_{i-1}-k)(p_{i-2}-k)\cdots$ where $k$ is a small positive integer

For $k=0$, there is: $p_i\# = (p_i)(p_{i-1})(p_{i-2})\cdots(5)(3)(2)$ For $k=1$, there is: $\varphi(p_i\#) = (p_i-1)(p_{i-1}-1)(p_{i-2}-1)\cdots(5-1)(3-1)(2-1)$ Is there any other notation that ...
1
vote
0answers
40 views

Comparative prime number theory with a small tweak

Fix $a, k \in \mathbb{N}$ relatively prime. For $x \in \mathbb{R}$ recall the function $$ \pi(x; k, a) = \sum_{\substack{p \leq x \\ p \equiv a \pmod{k}} } 1 $$ where $p$ denotes the primes. ...
1
vote
0answers
40 views

Is there a standard notation for the sequence of sorted exponents in the prime power factorization of a number?

Given some $n \in \mathbb{N}$, is there a name or notation for any/all of the following? The set of all factors $F(n)$ of $n$ (including 1 and $n$). The ascending sequence of non-unique prime ...
1
vote
0answers
53 views

Prime twins and $1 \mod 30$ confusion

Jie Wu improved Brun's theorem and showed that the number of prime twins up to $n$ satisfies for sufficiently large $n$ : $$\pi_2(n) < 4.5 \frac{n}{ln(n)^2} $$ However this confused me while ...
1
vote
0answers
70 views

Euclid's theorem: Paul Erdős's proof on the infinitude of primes

Seemingly simple question: Quote from Wikipedia: First note that every integer $n$ can be uniquely written as $rs^2$ where $r$ is square-free, or not divisible by any square numbers (let ...
1
vote
0answers
27 views

Maier's theorem

I have some questions with Maier's theorem https://en.wikipedia.org/wiki/Maier%27s_theorem If $1 < \lambda < 2$, then what? If $x+(\log x)^\lambda = x^{1+1/\pi(x)}$, then what? In particular, ...
1
vote
0answers
191 views

$\pi(z)-\omega(z-1)-\{-1,0,1\}= \pi(2z-1)- \pi(z)$ when $z(z-1)$ is divisible by all primes ${<}\sqrt{z}$

I have encountered the below problem: Given $z(z-1)$ divisible by all primes ${<}\sqrt{z}$ (and the prime factors of $z(z-1)$ are consecutive primes), prove (or disprove) ...
1
vote
0answers
45 views

Count of lower and upper primitive roots of prime $p \equiv 3 \bmod 4$

I was exploring the layout of primitive roots of primes over a reasonable range and this question concerns the number of primitive roots either side of $p/2$. Many primes have an exact match between ...
1
vote
0answers
27 views

Question on Newman's proof of the Prime Number Theorem

I am reading through Zagier's exposition of Newman's proof of the prime number theorem and I do not understand one of his arguments when proving his so called Analytic Theorem. This theorem states the ...
1
vote
0answers
32 views

When looking at the mod as binary value

Look at the next value: $$617*947 = 584299$$ 617, 947 are prime values. I want to see what are all the possible solutions for the next equation, for $k=4$: $$(a\mod k)(b\mod k) = 584299\mod k$$ ...
1
vote
0answers
66 views

Reasoning about $z^n = x^m + y^m$

Let $z,n,x,y,m$ be positive integers with $z \ge 5$ and $m \ge 3$ and $m$ odd. Does it follow that: $z$ cannot be prime if $p \ge 5$ and $p | z$, then either $p > m$ or $p|m$ Here is my ...
1
vote
0answers
153 views

Is $\frac{\text{next maximal}}{\text{maximal}} <= 2$ true?

Let $G_n(X)$ denote the $n^{th}$ record largest gap between consecutive primes below $X$, which some call maximal gap. Let $G_{n+1}(Y)$ denote the size of next larger maximal record gap in size from ...
1
vote
0answers
64 views

Can this approach to showing no positive integer solutions to $p^n = x^3 + y^3$ be generalized?

The following problem is a $2000$ Hungarian Olympiad question. Find all primes $p$ such that: $$p^n = x^3 + y^3$$ The answer is that there are only $2$ solutions: $2^1 = 1^3 + 1^3$ $3^2 = 2^3 + ...
1
vote
0answers
35 views

Lucas-Lehmer primality test and numbers form $k^{n}-1$

Is it possible to use Lucas-Lehmer test for testing the primality of numbers of the form $k^{n}-1$, where $k > 2$? For $k = 2$ (Mersenne number) $c_0 = 4$. What would be $c_0$ for $k > 2$?
1
vote
0answers
36 views

Bunyakovsky conjecture for cyclotomic polynomials

This article on Wikipedia: http://en.wikipedia.org/wiki/Bunyakovsky_conjecture says: In fact, it can be shown that if for all natural number $ n $, there exists a natural number $ x > 1 $ such ...
1
vote
0answers
34 views

Is there a better way to search a string so that I don't get false positives?

I've been using this equation to find primes of a specified range, in this example the range is 10 to 10000. Go ahead and try it out, your monitor will not catch fire. The problem I'm now having is ...
1
vote
0answers
90 views

Is every integer $\geq5$ the sum of two primes and a power of a prime?

Is every integer $\geq5$ the sum of two primes and a power of a prime (where $1$ is included in the prime powers)? I don't really expect someone to prove this here, but I wonder if the question has ...
1
vote
0answers
32 views

Solutions $n^2 = -1 \mod (p_n-1)$

Consider the equation $n^2 = -1 \mod (p_n-1)(*)$ where $p_n > n$ and $f(n) = p_n$ is the largest prime that satisfies the equation. $f(n)$ gives $p_n$ assuming there is a solution to the equation ...
1
vote
0answers
41 views

Has anyone established an upper bound for the least integer $k$ such that infinitely many primes have at most $k$ ones in their binary representation?

Has anyone established an upper bound for the least integer $k$ such that infinitely many primes have at most $k$ ones in their binary representation? $2$ is the only prime with $1$ one, the Fermat ...
1
vote
0answers
35 views

On integer $n>1$ and prime $p$ such that $p<n$ , $p$ does not divide $n$ and $n-p$ is a prime

Let $n>1$ be a given integer and $p$ be a prime less than $n$ and not dividing $n$ ; so $p$ and $n$ are co-prime ; hence $n-p$ and $n$ are also co-prime ; I would like to ask when is $n-p$ also is ...
1
vote
0answers
27 views

How quickly can we multiply hypercomplexes?

If we start with a hypercomplex number with $2^n$ entries, how quickly can we multiply it by another hypercomplex number, modulo a prime? EXAMPLE For example, with $n=1$, we get the complex numbers. ...
1
vote
0answers
36 views

Numbers with special factorisation

We know that any natural number $n$ can be decomposed as $p_1^{k_1}p_2^{k_2}...p_n^{k_n}$. I am looking for numbers which have $k_1=k_2=k_3=....=k_n=1$ i.e. given a number n, identify if it has all ...
1
vote
0answers
37 views

prime case function?

Does there exist a name (or assigned to a mathemtician) for a case function $f(x)$ in literature, such that it twould take the value $1$ when $x$ primes, and zero otherwise? I am just looking for a ...
1
vote
0answers
27 views

Composite residuosity statement.

Consider the following definition. A number $z$ is said to be $n$-th residue modulo $n^2$ , if there exists a number $y \in \mathbb{Z}_{n^2}^*$ such that $$z\equiv y^n \mod n^2$$ Let us take $n=6$ ...
1
vote
0answers
55 views

How many unique combinations of sets can we get?

Starting with $x$, which is a positive integer or zero, and $y$ a second positive integer or zero, with $y \ne x$, we can create lists. Set $p$ a prime greater than 2, $\alpha = (p-1)/2$, and ...
1
vote
0answers
54 views

Proving multiplicative property of euler's totient function $\phi$ using probability

If $m,n$ are co-prime , we know that $\phi(mn)=\phi(m)\phi(n)$. I want to prove it using probability. Probability that a selected number less than or equal to $mn$ is co-prime to $mn$ = ...
1
vote
0answers
37 views

Group, QR, QNR, Product of distinct primes

$N = pq$ where $p$ and $q$ are distinct primes. $ZN^*$ is all $x$ belonging to $ZN$ such that $gcd(x, N) = 1$. How do I find if $ZN^*$ is closed under addition? I believe $QR \times QR$ gives a ...
1
vote
0answers
83 views

Primality of Stirling numbers of second kind (again)

This question follows a previous one on the primality of Stirling numbers of the second kind ${n \brace k}$. Gerry indicated a paper on the topic. In this paper it is shown that for ${n \brace k}$ to ...
1
vote
0answers
23 views

How to split a list in n parts so the calculation time will be equal

I'm trying to implement a prime number finder. It as to find primes from 0 to X. I use this algorithm (performance may be questionable but this is not the question) to find the primes : ...
1
vote
0answers
25 views

Syndeticity and A.P.-richness of certain sets

Let $A \subset \mathbb{N}: \sum_{a \in A} (\frac{1}{a}) = \infty$; denote $\{ \alpha_1 @ \alpha_2: \alpha_1, \alpha_2 \in A \} = A @ A$, where "$@$" is any appropriate binary operator. (Note: $A$ is ...
1
vote
0answers
36 views

Fundamental Theorem of Arithmetic (Canonical) missing crucial step

I've worked long on the proof of the fundamental theorem of Arithmetic and there is only one tiny piece left I can't wrap my head around. Suppose that $$\prod_{i=1}^r p_i^{m_i} = \prod_{j=1}^s ...
1
vote
0answers
156 views

Remarks on a Previous Post

Recently I have been reading this post and I have noted something significant in the fake argument. As one can easily see that the basic idea behind the argument had been to show that the sequence ...
1
vote
0answers
50 views

The Existence of “Simple” Prime Generating Functions

Obviously, we do not know an explicit and easily manipulable formula for finding every prime - that is, a function $f(n)$ which yields the $n^{th}$ prime. I've seen plenty of formulas that "cheat" in ...
1
vote
0answers
36 views

Questions about primes made from consecutive numbers starting from 1

Similar to: Does there exist a prime that is only consecutive digits starting from 1? Let $b_n=\overline{a_1a_2a_3\dots a_n}$ and $a_n=n$. For example $b_{11}= 1234567891011$. I have a couple of ...