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
2answers
28 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
34 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 $ ...
0
votes
1answer
35 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
58 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
17 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
65 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} ...
1
vote
1answer
41 views

If $a|(p+1)$ for all but finitely many $p=3 (\text{ mod } 4)$ then $a$ divides $4$

I have the following question: Let $a$ be an integer such that $a$ divides $p+1$ for all but finitely many primes $p=3 \text{ mod } 4$ Can we conclude that $a$ must divide $4$? How we can prove ...
3
votes
1answer
41 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
62 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
72 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
69 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
140 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
47 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
53 views

Storing a natural number as a set of it's nth prime factors, how much data is used?

A natural number can be stored as its prime factors, for example: $10 = 2*5 = product(2, 5)\\12 = 2*2*3 = product(2, 2, 3)\\13 = 13 = product(13)$ And it's prime factors, being prime numbers, can be ...
1
vote
0answers
29 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
726 views

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

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
44 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
40 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
65 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
1answer
141 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
75 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
48 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 ...
2
votes
0answers
51 views

Greatest prime factor of $\left(\dfrac{n(n+1)}{2}\right)^2-1$.

Consider $$ \left(\dfrac{n(n+1)}{2}\right)^2-1. $$ Is is possible to say something about the lower bound on the greatest prime divisor of the above expression depending only on $n$? I surfed through ...
1
vote
0answers
42 views

Number theory problem of finding prime values p and q [duplicate]

Find all pairs of prime numbers $(p,q)$ such that $$p^3-q^5=(p+q)^2$$
8
votes
2answers
182 views

$\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ implies $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2}$; where $p>3$ is a prime?

From $\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ how does one get $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2},\,\forall a,b \in \mathbb N,\, a>b$; where $p>3$ is a prime ?
0
votes
0answers
52 views

Can this relationship be expressed algebraically?

$\frac{\left(x-1\right)!+1}{x}=\frac{\left(y-1\right)!+1}{y}$ When I graphed it, I noticed that it bears a resemblance with the equation (which could of course be completely coincidental): ...
0
votes
1answer
42 views

Show $ \left\lfloor\frac{2n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \in \{ 0, 1 \}$

I conjecture that $$ \left\lfloor\frac{2n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \in \{ 0, 1 \}. $$ I know that it is always nonnegative, and equals $1$ for $n < p \le 2n$, ...