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

1
vote
0answers
55 views

Showing that $U_n$ and $U_m$ must have primes between them

Given that $$U_n=\underbrace{1\cdots1}_{n\text{ times}}$$ and $n >2$, how can one show that if $m$ and $n$ have primes between them, then $U_n$ and $U_m$ must also have primes between them? ...
1
vote
1answer
57 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
58 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
44 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 ...
0
votes
5answers
707 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?
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
19 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
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 ...
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 ...
8
votes
2answers
170 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 ?
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 ...
4
votes
2answers
125 views

Diophantine Equation $ x^n + y^n =z^n (x<y, n>2) $

I am looking for simple college level algebraic solution to prove that $x$ and $y$ ($x$ < $y$) for the above equation can't be prime numbers. (I know more complex and involved solution using high ...
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. ...
9
votes
1answer
127 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 ...
-7
votes
2answers
65 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.
6
votes
4answers
256 views

Currently, what is the largest publicly known prime number such that all prime numbers less than it are known?

So recently, an absurdly large prime number was found, but a lot of prime numbers less than it are still not known. I am wondering up to where we know all the primes. I put "currently publicly known" ...
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?
4
votes
4answers
30k views

What is a co-prime?

I've never encountered this question in any of my math classes and it just shows up randomly in my comsci class with no further info about it. I've wiki'ed it, but can't even understand that. Could ...
-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 ...
4
votes
2answers
218 views

$h+k=p-1$, $p$ prime. Prove $h!k! + (-1)^h \equiv 0 \pmod{p}$?

Suppose that $p$ is a prime. Suppose further that $h$ and $k$ are non-negative integers such that $h + k = p − 1$. I want to prove that $h!k! + (−1)^h \equiv 0 \pmod{p}$ My first thought is that by ...
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 ...
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
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. ...
5
votes
2answers
477 views

Sum of two primes

In how many ways can $10001$ be written as the sum of two primes? Obviously since the 10001 is odd, one of the primes must be $2$. This leaves the second, must be prime as 9999, but it isn't, hence ...
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
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 ...
6
votes
1answer
40 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 ...
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$, ...
27
votes
6answers
3k views

Percentage of primes among the natural numbers

How high is the percentage of primes in $\mathbb{N}$? ($\mathbb{N} := \lbrace { 1, 2, 3, \ldots \rbrace }$ ; a prime is only divisible by itself and 1 in $\mathbb{N}$) The percentage has to be lower ...
4
votes
1answer
34 views

Solving a Diophantine equation with LTE

Show that only positive integer value of $a$ for which $$4(a^n+1)$$ is a perfect cube for all positive integers $n$, is $1$. Rewriting the equation we obtain: $$4(a^n+1)=k^3$$ It is obvious that $k$ ...
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 ...
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, ...
6
votes
2answers
83 views

What are the necessary conditions for UPC primes?

0 68000 00027 7 is a UPC that the Hershey Company could use for some candy bar or other product. It happens that $6800000027$ is a prime number. But $68000000277$ ...
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 ...
1
vote
1answer
72 views

Confusion on Mersenne Numbers

One fundamental theorem on Mersenne Numbers states: If $q$ is a prime of the form $8k+7, q|M_{(q-1)/2}=2^{(q-1)/2}-1$. Let $q=7+768z$, So ...
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 ...
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 ...
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 ...
3
votes
2answers
597 views

Questions regarding p-adic expansion and numbers

As opposed to real number expansions which extend to the right as sums of ever smaller, increasingly negative powers of the base $p$, $p$-adic numbers may expand to the left forever, a property ...
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
12
votes
2answers
543 views

Diophantine equation involving prime numbers : $p^3 - q^5 = (p+q)^2$

Find all pairs of prime nummbers $p,q$ such that $p^3 - q^5 = (p+q)^2$. It's obvious that $p>q$ and $q=2$ doesn't work, then both $p,q$ are odd. Assuming $p = q + 2k$ we conclude, by the equation, ...
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 ...
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$, ...