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
59 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, ...
5
votes
0answers
61 views

Is this a known series?

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
45 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 ...
2
votes
2answers
45 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
23 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\ ...
0
votes
5answers
710 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
39 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
81 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
66 views

Find the prime number [on hold]

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? [on hold]

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
128 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
34 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
33 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
32 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
71 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
41 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
61 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
306 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
62 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
66 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
171 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$, ...
4
votes
5answers
67 views

$p$ divides $n^p-n$

Its very easy to prove $p\mid n^p-n$ for p=3,5,7, it fails for p=9 because $$ (n+1)^9-(n+1)= n^9+9n^8+36n^7+84n^6+126n^5+126n^4+84 n^3+36n^2+8n $$ and $84= 2²\times 3\times7$. Is it true for ...
3
votes
2answers
30 views

Show $ \frac{1}{n} \sum_{p \in \mathbb P} \left\lfloor \frac{n}{p} \right\rfloor \log p = \log n + O(1)$

Any hints how to prove for $n \in \mathbb N$ $$ \frac{1}{n} \sum_{p \in \mathbb P} \left\lfloor \frac{n}{p} \right\rfloor \log p = \log n + O(1) $$ where $\mathbb P$ denotes the set of all primes? As ...
3
votes
1answer
44 views

Can $\sigma(n)-n$ be a proper divisor of $n$?

Let $n\ge 2$ be a natural number, $\sigma(n)$ the sum of its divisors. Can $\sigma(n)-n$ be a PROPER divisor of $n$ ? If $\sigma(n)-n=n$ , $n$ is a perfect number. If $\sigma(n)-n=1$ , $n$ is a ...
0
votes
0answers
38 views

All primes in the form 4x + 1 can be written as a sum of two squares. [duplicate]

Because all primes other than 2 are odd, one of the two perfect squares must be odd, with the other being even. Is there any way to prove the statement, or is it just an observation?
0
votes
0answers
28 views

Probabilistic primality test for Mersenne numbers

Maybe you know of any probabilistic algorithms specifically checking primality Mersenne numbers? I am not talking here about a universal algorithm (example: the Miller-Rabin test). I'm talking about ...
4
votes
1answer
23 views

Prove that for any prime $p$, if $a>b$ then $p^2$ divides $C(pa,pb)-C(a,b)$.

Let, $p$ be a prime and $a>b$. If $\operatorname{C}(n,r)$ denotes the combination of $r$ objects from a collection of $n$ objects taken at a time, prove that ...
1
vote
0answers
79 views

$p$ be a prime number , then is it true that $p^2| {pa \choose pb}-{a \choose b} , \forall a,b \in \mathbb N$ ?

Let $p$ be a prime number , then is it true that $p^2| {pa \choose pb}-{a \choose b} , \forall a,b \in \mathbb N$ ?
1
vote
1answer
23 views

Clarification of a proof of Eisenstein's lemma

I'm working on a proof of quadratic reciprocity following Wikipedia's proof via Eisenstein, and one line in the proof seems unjustified: On the other hand, by the definition of $r(u)$ and the ...
6
votes
0answers
67 views

A bound on the nth prime.

Is there any combinatorial argument to show that the nth prime $p_n = \mathcal{O}(n^k)$ for fixed $k$ ? There is a problem in the book by Apostol to find upper bounds on $p_n$, the Prime Number ...
5
votes
1answer
74 views

Can $2^{M^N}+M^{N^2}$, where $M$ and $N$ are odd primes, never be a prime?

Q: Is number of the form $$\displaystyle 2^{M^N}+M^{N^2}$$ always composite for $M,N$ odd primes? I observed that: If $M=N$ then this number is absolutely a composite, because it satisfies the ...
0
votes
1answer
49 views

Is this a valid equivalent expression of the twin prime conjecture?

The twin prime conjecture states that it is possible to find two primes $p$, $p+2$ at a distance $2$ that are as big as wanted (Wikipedia). I am learning about the basic properties associated to the ...
2
votes
0answers
20 views

Generalization of a Result Concerning Projective Planes

Let $\mathcal P$ denote the set of all possible orders of projective planes. For $q\in\mathcal P$, let $PG_2(q)$ denote the projective plane of order $q$. There is a theorem due to James Singler ...
3
votes
2answers
419 views

Is it a composite number? [duplicate]

How do I prove $19\cdot8^n+17$ is a composite number? Or is that number just a prime? So I tried to find a divisor in the cases $ n = 2k $ and $ n = 2k + 1 $. But I had no success. Do you have any ...