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

4
votes
1answer
360 views

Is there a polynomial-time algorithm to find a prime larger than $n$?

Is there a polynomial-time algorithm to find a prime larger than $n$? If Cramér's conjecture is true, we can use AKS to test $n+1$, $n+2$, etc. until the next prime is found, and this method will ...
1
vote
1answer
70 views

What can I say about $x^4 \equiv -4 \mod p$ where $p$ is prime?

What can I say about $x^4 \equiv -4 \mod p$ where $p$ is prime? In general what can I do with powers that are greater than $2$ and where I cannot use reciprocity, legendre/jacobi etc... In general ...
0
votes
1answer
36 views

Modular equivalence for base ten

What does $10^{a} \equiv 1 \pmod{p}$ mean? Especially when relating it to base 10 referring to $10^{a}$?
1
vote
1answer
126 views

What is name of conjecture? [duplicate]

Possible Duplicate: Every even integer can be expressed as the difference of two primes? there is one conjecture that I do not know what they are called. This is: Every even number can be ...
0
votes
2answers
85 views

Conclusion from exponential equivalence modulo prime

Given that i have: $$10^{a} \equiv 10^{b} \pmod p$$ and we know that: $$a > b$$ Can we say that b is a multiple of a or this is not valid? thanks,
3
votes
1answer
179 views

Checking divisibility of prime number using digit count

Given a number $n$ and a prime number $p$, we aim to divide $n$ into $r$ digit numbers and sum them to check $n$'s divisibility by $p$. I'm asked to prove that $r$ is a divisor of $p-1$. I think that ...
12
votes
2answers
475 views

Prime one heap Nim

I have been working on an interesting problem my lecturer mentioned recently. Prime Nim is a variant of the Nim game where you have a single pile with an arbitrary number $n\in \Bbb N+\{0\}$ of ...
2
votes
1answer
161 views

A product over primes and its limit

Let $n$ be a positive integer and let $p(n)$ be the $n$th prime. Let $$f(n) = \dfrac{1}{30} \prod_{3<i<n+1} \left(\dfrac{p(i)- \left( \dfrac{2i}{\ln(p(i))}\right) + 1}{p(i)} \right).$$ How does ...
4
votes
2answers
1k views

Bijection between Prime numbers and Natural numbers

We know that if set $S$ is countable then this set and set of all natural numbers are equivalent, which means that there must be some bijection between this two sets $F:S\rightarrow N$. We know that ...
0
votes
1answer
84 views

primes, patterns, recognizable

The pairs $6h-1$ and $6h+1$ are not twin primes, that is at least one of them is factorizable/decomposable, where $h$ can be found from any of the following equations: $$ \begin{align} h = 6t_1t_2 ...
1
vote
2answers
115 views

primes and patterns/representations

As we know that primes other than 2 and 3 can be expressible as: $p \equiv 1\pmod{6}$ or $p \equiv -1\pmod{6}$. In other words, 6|(p-1) or 6|(p+1). Or, p = 6h+1 or 6h-1. Now, for any integer h, ...
3
votes
0answers
259 views

Question about recursive defined functions.

This question is about counting functions. With counting functions $F$ I mean functions from the positive integers to the positive integers that are strictly nondecreasing and can grow no faster than ...
3
votes
1answer
139 views

Prove that all divisors of $\frac{p^p-1}{p-1}$ are of the form $pk+1$ where $p$ is prime and $k\in\mathbb{Z}$.

Prove that all divisors of $$\frac{p^p-1}{p-1}$$ are of the form $pk+1$ where $p$ is prime and $k\in\mathbb{Z}$.
0
votes
3answers
242 views

The number of possible factorizations of a positive integer.

Given a positive integer $n>1$ with prime factorization $$n=\prod_{p_i \text{ prime}}p_i^{k_i}, \space i\ge1, \space k_i \in \mathbb N^*$$ how can I compute the number of factorizations of ...
2
votes
1answer
1k views

Primitive roots modulo a prime number

Suppose $p$ is a prime number. I want to show that if integers $a,b$ are such that $p$ does not divide $b$ and for any $y$ which has the properties (1) $y$ is not divisible by $p$ and not a ...
3
votes
3answers
810 views

Prime factorization knowing n and Euler's function

My task is to factorize $n$ knowing it has two factors and $\varphi(n)$. How can I do it? Thanks for any advice.
3
votes
1answer
179 views

Modifying Euler Totient Function

To calculate the number of integers co-prime to $N$ and less than $N$ we can simply calculate its ETF (Euler's totient function). However to calculate the number of integers co-prime to $N$ but less ...
0
votes
3answers
154 views

Possibility of having exactly 5 primes in a sequence of $10$ consecutive positive integers.

Does a sequence of positive integers $a_n$ such that the sequence $a_n, \space a_n+1,\space a_n+2,\space \cdots, \space a_n+9$ contains exactly $5$ primes exist? Is such sequence finite or infinite? ...
3
votes
2answers
69 views

Why doesn't work Integer factorization for fields?

I try to unterstand, why the Integer factorization is only working for rings and not for fields. My first idea was, that you don't have a uniqueness quantification for prime "numbers" in fields. Is ...
1
vote
1answer
138 views

Mertens' asymptotic formula for $\prod \left(1-p^{-1}\right)$ without constant

I've heard that there is an easy way to derive the asymptotic $$\prod_{p\le x} \left(1-\frac{1}{p}\right) \sim \frac{c}{\log(x)}$$ if one isn't interested in deriving $c=e^{-\gamma}$. I don't see how ...
2
votes
6answers
119 views

help with this assertion: The only number divisible by 3 and that is prime is 3

I have encountered this phrase within a proof by prime numbers and couldn't figure out if it is true. Is there any proof lurking around for this fact? thanks!
2
votes
0answers
58 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 ...
1
vote
0answers
93 views

Is This a Good Prime Sieve?

I have played around with deriving a Boolean IsPrime function. http://science.niuz.biz/boolean-t313980.html?s=5e8b6805a1b73daa7c1062fabbe74e90 I have found a simple method for deriving a single ...
2
votes
2answers
52 views

Is there any way to split a number with multiplication of some prime number

I am looking for an algorithm which helps me split a number $N$ as such: $$N=p_1^a p_2^b \cdots p_n^z$$ where $N$ is the given number, $p$ is prime numbers smallest to greatest, and $a,b,\cdots,z$ ...
0
votes
1answer
212 views

Showing $f(x)$ is constant.

Let $f(x)=a_nx^n+...a_1x+a_0$ is an integer polynomial with $a_n>0,n\not=1$. $f(p)$ is prime for every $p$, where $p$ is prime. How to show $f(x)$ is constant, or not?
5
votes
1answer
3k views

How many numbers in a given range are coprime to N?

Is there a good algorithm for counting the numbers $x$ between $A$ and $B$ with $x$ and $N$ coprime? This is just like this question except for the range. The factorization of $N$ is known. I ...
4
votes
1answer
146 views

Why are Mersenne primes easier to find?

9 out of 10 biggest known prime numbers are Mersenne numbers. Are they easier to find? ...
1
vote
2answers
227 views

What is the least residue mod $N = 95$ of $3^{1.1 \cdot 10^{43}}$?

This is a practice problem. Since $5 \cdot 19$ are prime factors of $95$ I tried to break it into two congruence equations and use CRT, but I can't seem to work this out. By Fermat's little theorem we ...
3
votes
0answers
148 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" ...
7
votes
2answers
1k views

What prime numbers have the sum of their digits as a prime number?

(Meta comment: Congrats to Andre Nicolas! I am happy for Andre Nicolas that he is second ranked now. Also he has 3001 answers with no questions. That is good. I am also glad to see Arturo Magidin has ...
2
votes
0answers
74 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 ...
3
votes
0answers
123 views

Gram's series for integral equation

The prime counting function $ \pi(x) $ satisfies the integral equation $$ \log\zeta (s)= s\int_{0}^{\infty}dx \frac{ \pi (e^{t})}{e^{st}-1} \tag{0}$$ and it has the solution in terms of Gram's ...
0
votes
1answer
144 views

On the probability that $ 2x^2 + 1 $ is prime (quadratic residue)

I tried to compute the multiplicative inverse of the probability that $ 2 x^2 +1 $ is prime. (I'm aware that proving there are infinitely many such primes is not done yet, but let's ignore that for ...
3
votes
1answer
86 views

Convergence of $ \sum_{n=1}^\infty (p_n)^{-n}$

How to determine the convergence of $$ \sum_{n=1}^\infty (p_n)^{-n}, $$ where $p_n$ is the $n$th prime?
2
votes
1answer
965 views

Difference Between Primes

We know that there are two prime numbers that have a difference of one: 2 and 3. And we know there is at least one pair of primes with a difference of two: 5 and 7. Same with a difference of three: 2 ...
3
votes
4answers
1k views

Prime, followed by the cube of a prime, followed by the square of a prime. Other examples?

The numbers 7, 8, 9, apart from being part of a really lame math joke, also have a unique property. Consecutively, they are a prime number, followed by the cube of a prime, followed by the square of a ...
8
votes
2answers
2k views

It it possible to “compress” a list of large numbers using their prime factors?

On a computer I can have integers on arbitrary size thanks to GMP, so it's represented in base 2 in memory. I'm wondering if it's possible in theory to use less memory if I store only prime factors ...
1
vote
3answers
226 views

Equation involving reciprocal of prime numbers

I have the following problem: given a prime number $p_k$ and the prime immediately following $p_{k+1}$, is it possible to find a prime number $q$, with $q\ne p_k$ and $q\ne p_{k+1}$ such that the ...
3
votes
0answers
96 views

Goldbach-like conjecture

While experimenting, I found that every number up to 200000 except 216 is the sum of a prime and a triangular number (where 0 and 1 are included as prime). Is anything known about this?
5
votes
0answers
135 views

Is the application of $\mu$ on $P_x(s)^k$ analogous to the differentiation $\frac{d^k f(\lambda) }{d\lambda^k}\biggr|_{\lambda=0}$?

Let me start with the following on elementary symmetric polynomials: The elementary symmetric polynomials appear when we expand a linear factorization of a monic polynomial: we have the identity ...
1
vote
0answers
167 views

Matiyasevich polynomial proof

Can someone provide a proof, or a link to a proof, of why does the Matiyasevich polynomial always generate primes for the nonnegative results? Any help will be appreciated.
3
votes
1answer
430 views

Longest Odd/Even Sequence in Composite Patterns

NOTE I have completely reworded this because I made a complete hash of it the first time, it got worse as I added to it. I apologize to anyone who might have been confused, and hope that this will be ...
2
votes
3answers
773 views

What prime number generating algorithms are used?

You sometimes hear bout these huge prime numbers (RSA prime number challenge comes to mind) and I was curious about what algorithms or formulas prime-number generators use in practice ? For example in ...
1
vote
3answers
86 views

Solving equations of form $3^n - 1 \bmod{k} = 0$, $k$ prime

In particular, I've used python to brute-force results of $3^n-1\bmod{7} = 0$ but was hoping there is a more elegant method.
2
votes
2answers
1k views

Expressing a Non Negative Integer as Sums of Two Squares

I'm writing a code in C that returns the number of times a non negative integer can be expressed as sums of perfect squares of two non negative integers. ...
8
votes
3answers
495 views

First-order proof that there is no largest prime

Is there a first-order proof on $(\mathbb{N},+,*,\le)$ that there is no upper bound on primes. ie that $$\neg\exists{q}{\forall{p}{(\forall{m,n}\space m*n=p\rightarrow m=1\vee n=1)\rightarrow p\le ...
0
votes
1answer
44 views

Regarding one form of potential primes

If we think of primes of the form $a^n-b^n,$ where $a,b,n$ are positive natural numbers and $a>b$, $(a-b)\mid (a^n-b^n)$, so $a-b$ must be $1$ and $n$ must be prime else $(a^r-b^r)\mid (a^n-b^n)$ ...
3
votes
2answers
3k views

Prime factors of a positive integer greater than its square root

"Every composite positive integer has at least one prime factor less than the square root of the integer." Proof by contradiction: If $p_1, p_2, ..., p_n$ are prime factors of $x$ greater than ...
1
vote
2answers
246 views

Is there a way to show that $\sqrt{p_{n}} < n$?

Is there a way to show that $\sqrt{p_{n}} < n$? In this article, I show that $f_{2}(x)=\frac{x}{ln(x)} - \sqrt{x}$ is ascending, for $\forall x\geq e^{2}$. As a result, $\forall n \geq 3$ ...
2
votes
1answer
187 views

2 dimensional cellular automaton for prime twins?

Is there a 'simple' 2 dimensional cellular automaton to generate all prime twins ? With 'simple' I mean not too many states per cell and not so many rules. Thus a universal turing machine equivalent ...