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
1answer
56 views

Proof that $2^n-1$ does not always generate primes when primes are plugged in for $n$?

Exactly what the name entails. The function $2^n-1$ I see largely tends to generate primes when $n$ is prime. However, a week ago I heard that this was horribly false. Please show me a disproof.
-1
votes
0answers
28 views

Is there a function that shows n!-lcm(1,2,3…n)?

1!-lcm(1)=0 2!-lcm(1,2)=0 3!-lcm(1,2,3)=0 4!-lcm(1,2,3,4)=12 5!-lcm(1,2,3,4,5)=60 I have not looked into this incredibly deeply, but I found that there may be some sort of connection with primes, ...
0
votes
0answers
326 views

Can this we define the zeta function like this?

Background We define a smooth continuous function function where: $$ p(i) = p_i $$ where $p_i$ is the i'th prime. We also define the following series: $$ \alpha(s) = (\ln(2))^s + (\ln(3))^s + ...
-1
votes
0answers
25 views

What interesting results can be drawn from this expression?

What interesting results can we draw from this expression? $$\zeta(s)=\left(1+\sum_{r>0}\sum_{\{r\}}\prod_{j=1}^t \frac {(-1)^{i_j}}{{i_j}!}\left(\frac {P({r_j}\cdot ...
10
votes
4answers
346 views

Is there a function that can be subtracted from the sum of reciprocals of primes to make the series convergent

The gamma constant is defined by an equation where the harmonic series is subtracted by the natural logarithm: $$\gamma = \lim_{n \rightarrow \infty }\left(\sum_{k=1}^n \frac{1}{k} - \ln(n)\right)$$ ...
2
votes
3answers
39 views

Proving that $i! \mid (p-1)\cdot(p-2)\cdots(p-i+1)$ for $i < p$

Started solving this problem: $$ (a+b)^p \equiv a^p+b^p \pmod{p}$$ where $p\in\mathbb{P}$, $a,b\in\mathbb{Z} $ After a few implications I arrived to this $$ i! \mid ...
4
votes
4answers
75 views

what is the greatest integer that divides $p^4-1$ for every prime number p greater than 5

what is the greatest integer that divides $p^4-1$ for every prime number p greater than 5(this is a gre subject math problem) I think that $p^4-1=(p^2+1)(p-1)(p+1)$,so 8 must divide all the $p^4-1$ ...
3
votes
1answer
45 views

Inverse of prime counting function

The prime counting function $ \pi (x) \approx \dfrac {x} {\ln(x-1)} $. This function returns the number of primes less than $x$. Note: $x-1$ gives a better estimate than $x$. How to find $x$ given $ ...
1
vote
1answer
42 views

If Wieferich primes are finite…Then what?

I am wondering if $1093$ and $3511$ are the only Wieferich Primes, then what would it imply? (A wieferich prime is a prime satisfying the congruence $2^{p-1}\equiv 1\ mod \ p^2 $). I know of 3 cases; ...
0
votes
1answer
65 views

Are all even numbers the difference of prime powers

Does there exist an even positive integer greater than $100$ (to eliminate trivial cases) that cannot be expressed in the form: $p^2-q$ $p-q^2$ $p^2-q^2$ $p^3-q^3$ where $p$ and $q$ are primes.
1
vote
0answers
19 views

Quadratic polynomials describe the diagonal lines in the Ulam-Spiral

I'm trying to understand why is it possible to describe every diagonal line in the Ulam-Spiral with an quadratic polynomial $$2n\cdot(2n+b)+a = 4n^2 + 2nb +a$$ for $a, b \in \mathbb{N}$ and $n \in ...
6
votes
1answer
67 views

Is $\pi(n)$ a Rational Function?

Are there some two-variable polynomials $P(n,\log n)$ and $Q(n,\log n)$ which we have the bellow equation for prime counting function $\pi(n)$ for $n \in \mathbb{n}$? $$\pi(n) = \Bigl{\lfloor} ...
3
votes
1answer
42 views

Prime Zeta Function proof help: Why are these expressions not equal?

I was trying to create a formula for the Prime Zeta function and I partially succeeded except for one frustrating error. I was only able to formulate an approximation. Consider the following sum: ...
2
votes
2answers
67 views

$\pi(x)$ Proof Clarification

In a proof from a number theory book that $${\pi(x) \over x}\le {2k \over x} + {\phi(k) \over k}$$ Where $x=kl+r$ with $0 \le r\lt k $ It is stated that $$\pi(x) \le k+(l-1)\phi(k) + r \le 2k+{x\over ...
3
votes
1answer
40 views

Usefulness of prime numbers as Threading Timeouts in programming [on hold]

I am a .NET programmer, founded in math. I am having an argument with a fellow programmer. When I add a Threaded Timer to the program, the interval in milliseconds I use is always a prime number. ...
0
votes
1answer
78 views

Is $u_n$ where $\left\{\begin{matrix}u_{1}=5 \\ u_{n}=\frac{2^{u_{n-1}}+1}{3} \end{matrix}\right.$ always prime?

$\left\{\begin{matrix}u_{1}=5 \\ u_{n}=\frac{2^{u_{n-1}}+1}{3} \end{matrix}\right.$ I conjecture that $u_{n}$ is prime number. But I can not prove it. So I want to know my conjecture is right or ...
0
votes
1answer
56 views

Does $\pi \left(\dfrac{x+y}{2}\right)=\pi\left(\sqrt{xy}\right)$ hold for infinitely many values of $x$ and $y$?

The problem is (assume $\pi(x)$ to be the prime-counting function), Does there exist infinitely many solutions to the equality $\pi \left(\dfrac{x+y}{2}\right)=\pi\left(\sqrt{xy}\right)$ with ...
0
votes
1answer
71 views

Is the Riemann zeta function $\zeta(s)$ exactly $\pi(x)$?

Let $\pi(x)$ denote the number of primes less than or equal to a certain x value. The prime number theorem says that $x/\log x$ (or more accurately $x/(\log x-1)$) has been the most popular method ...
2
votes
1answer
68 views

Are 7 and 49 coprime?

Or 6 and 36, 5 and 30, and things like that. They aren't, right? A co prime is a pair of numbers whose greatest common factor is 1. They (7 and 49) share 7 as well as 1. If 7 and 49 aren't co prime, ...
7
votes
0answers
145 views

What is known about the sum $\sum\frac1{p^p}$ of reciprocals of primes raised to themselves?

Consider the following series: $$\sum_{p\in\mathcal{P}}\frac{1}{p^p}$$ where $\mathcal{P}$ is the set of all prime numbers: $\mathcal{P}=\{2,3,5,7,11,13,\ldots\}$. My question is: Is this a ...
5
votes
5answers
48 views

Is it allowed to define a number system where a number has more than 1 representation?

I was just curious; is it allowed for a number system to allow more than one representation for a number? For example, if I define a number system as follows: 1st digit (from right) is worth 1. 2nd ...
3
votes
3answers
70 views

Storing a natural number as a set of its Nth prime factors, how much data is used?

Spoiler, tap to reveal. In asking the following question, I knew that each natural number could be prime factorised. However I assumed that most natural numbers would each be equal to the ...
1
vote
0answers
30 views

sextic reciprocity and divisibility question

Regarding the question if $p|(2^{2(p-1)/6}+2^{(p-1)/6}+1) $ where $p$ is a prime of the form $7\mod 8 $ That is how far I got: $2^{(p-1)/6} \mod\ p\equiv x $ if the solution of $x^6\ mod\ ...
1
vote
5answers
728 views

why only square root approach to check number is prime [closed]

Why do we use only square root approach to find a number is prime or not? why not cube root & 4rth root?
1
vote
0answers
46 views

Given a number $N$ and a prime $P$, how many numbers $\leq N$ are divisable by P but not by any smaller primes?

The following Math Exchange question deals with a similar problem: not divisible by 2,3 or 5 but divisible by 7 However, the answers given become infeasible quite quickly because the amount of ...
1
vote
1answer
89 views

how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime?

Given that $$U_n=\underbrace{1\cdots1}_{n\text{ times}}$$ and $n >2$, how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime? Because $U_m= ...
2
votes
1answer
41 views

Why is $x^{100} = 1 \mod 1000$ if $x < 1000$ and $\gcd (x,1000) = 1$?

Let $U(1000) =$ the multiplicative group of all integers less than and relative prime to $1000$. "Show that for every $x \in U(1000)$ it is true that $x^{100} = 1 \mod 1000$." Been thinking ...
1
vote
1answer
23 views

$p$ and $r$ are primes greater than $2$. $p+r$ vs $p+2r$, which could be a prime number?

For $p+2r$, a example would be $3$ and $5$. Since $6+5 = 11$, I am led to believe $p+2r$ to be the right answer. But I don't know how it works?
1
vote
1answer
31 views

Trouble with a proof: $(p^n - 1 , e)=1$ for $e\in \mathbb{N}$, p prime

I'm having trouble understanding a proof. The Lemma states: For every natural number $e$ there are infinitely many prime powers $q$ with $(q-1,e)=1$. The prove is as follows: Write $e=2^km$, m odd. ...
4
votes
0answers
47 views

What is currently the biggest prime number with no smaller undiscovered prime number? [duplicate]

Just out of curiosity, what is currently the biggest discovered prime number with no smaller undiscovered prime number?
-7
votes
2answers
67 views

Find the prime number [closed]

Find all prime numbers $a,b,c$ and positive integers $k$ satisfying the equation $a^2 + b^2 + 16c^2=9k^2+1$. I tried but I didn't came to any result.
-5
votes
1answer
66 views

Does there exist a prime that is a sum of two prime power towers? [closed]

Does there exist prime number of the form $$\huge 2^{3^{5^{\,.^{.^{.\,^{p_n}}}}}} + p_n^{p_{n-1}^{\,.^{.^{.\,^{3^{2}}}}}}$$ where $p_n$ is the $n$-th prime number(and both towers are running through ...
1
vote
1answer
60 views

prove that $p(n) := n^2 + n + c$ is not prime

The question is in MIT Mathematics for CS assignments but unfortunately there is no solutions. -> I do understand that it is false if we use $n = c$ or $n = c-1$ but cannot formally write it as ...
2
votes
1answer
52 views

Is it correct to say a number $n$ is prime if $n \bmod a \neq 0$ for $2 \leq a \leq\sqrt n$?

As I was playing around with Fermat's little theorem, I came up with another method to check if numbers are prime, if the remainder of the division of $n \over a$ was not $0$ for any integer a between ...
9
votes
0answers
151 views

Showing that the Prime Number Theorem is Plausible.

I have started to work through the course notes titled "Integers, Polynomials and Finite Fields" by Kenneth Davidson to keep me busy this summer, and there is a question in here This is an ...
1
vote
1answer
30 views

Average smallest prime factors

I looked at the average smallest prime factor (ASPF) for the numbers up to N: $\text{ASPF}(N) = \frac{1}{N-1}\ \Sigma_{k=2}^N \text{SPF}(k)$ ASPF(100) = 13 ASPF(1,000) = 79 ASPR(10,000) = 578 ...
5
votes
0answers
35 views

Why are there palindromic subsequences at random among this sequence?

So I was thinking about the Goldbach conjecture and I rephrased it to myself as the following: Prove that every number lies halfway between two primes (or is itself prime.) Which is equivalent. ...
1
vote
1answer
34 views

List all elements in the residue field $Z[i]/(q)$

Consider a Gaußian prime $q$. How to list all elements in the residue field $Z[i]/(q)$? Is there any formulas or criteria? Here I'm looking for the case $q$ is a complex number, as I can do the real ...
1
vote
0answers
34 views

Ulam spiral and triangular numbers

Is there any explanation for the twister-like pattern build by triangular numbers $$\Delta_n = \frac{n\cdot(n+1)}{2}$$ in the Ulam Spiral? Here for $1,\ldots,900$:
11
votes
1answer
72 views

How many unique numbers can be obtained from multiplying two natural numbers less than $N$?

The question seems simple, but I cannot wrap my head around how to properly count it, or even give a good estimate. I can't find the answer either. We have two integer numbers $1 < a,b < N$, ...
6
votes
1answer
42 views

Are Pythagorean triples $(a,b=\frac{a^2-1}{2},c=\frac{a^2-1}{2}+1)$ able to generate always primes through this property?

I was testing the properties of the Pythagorean triples of the form $(a,b=\frac{a^2-1}{2},c=\frac{a^2-1}{2}+1)$ and by chance I found that the following expression seems to be true for all the pairs ...
2
votes
2answers
63 views

Are there any primes for which $a^2 = pb^2 + 1$ does not exist?

The smallest solution to the above equation for various primes are: $(p=2)$ $3^2 = 2*2^2 +1$ $(p=3)$ $2^2 = 2*1^2 +1$ $(p=5)$ $9^2 = 5*4^2 +1$ $(p=7)$ $8^2 = 7*3^2 +1$ Is there at least one ...
0
votes
2answers
23 views

Prove $a,2a,\ldots,(p-1)a$ leave different remainders mod $p$

Say $p$ is a prime number and we have $a,2a,\ldots,(p-1)a$, if you then take any $ a \bmod p$ in the range of our $a$s they will all have different remainders, as long as $a$ is not $\equiv 0 ...
11
votes
3answers
185 views

Digital root of twin prime semiprimes

It appears that the product of any pair of twin primes (excluding the first pair 3 and 5) yields a semi prime whose digital root is equal to $8$. Example: $$ 17 \cdot 19 = 323 $$ The digital root of ...
5
votes
3answers
308 views

Understanding isPrime function from Wikipedia, a function that determines if a number is prime

I know there are several questions on how to determine if a number is prime but none of them help me understand this particular implementation on Wikipedia, ...
4
votes
2answers
76 views

a practical prime counting function

Looking at Prime counting functions on Wikipedia, I only found formulas with no hint on how people got there. So, to better understand, I've decided to build one from scratch, starting from a naive ...
1
vote
2answers
57 views

Are there infinitely many primes of form $a^n+1$ for fixed even $n$?

Fix an even integer $n\geq 2$. Are there infinitely many primes of the form $a^n+1$, where $a$ is an integer? Is there some theorem covering this, or is the problem still open for all even $n$?
1
vote
1answer
49 views

Finding modulo inverse if gcd is not 1

I have to find $$\frac{p^e-1}{p-1} \bmod 1000000007,$$ where $p$ is a prime number. If $\gcd(p-1,1000000007)$ is not $1$, since modular inverse of $p-1$ is not defined. Also, (p^e-1) is divisible by ...
4
votes
1answer
67 views

A good book on humankind’s understanding of primes?

I might be interested in a good book on what humankind knows about primes as of now, preferably put into historical context. It should rather be something about the big picture than a comprehensive ...
4
votes
2answers
236 views

Prime numbers, and their digital roots.

Edit It is clear that this conjecture is false, in many, many circumstances, and I am grateful to the whole Math Stack Exchange community for helping me to see this. Thank you! Let $p \in ...