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
3answers
55 views

Finding all prime numbers $p$ such that $p^a + p^b$ is a perfect square

Find all prime numbers $p$ and positive integers $a$ and $b$ such that $p^a + p^b$ a perfect square. How can I find this. I have no idea about this problem.
1
vote
0answers
19 views

Group, QR, QNR, Product of distinct primes

$N = pq$ where $p$ and $q$ are distinct primes. $ZN^*$ is all $x$ belonging to $ZN$ such that $gcd(x, N) = 1$. How do I find if $ZN^*$ is closed under addition? I believe $QR \times QR$ gives a ...
0
votes
3answers
88 views

What is the definition of prime number?

Every number has the factors of $1$, itself, $-1$, and the negative version of itself (itself multiplied by $-1$). So let's take for example $5$, it has the factors: $ 1$ $ 5$ $-1$ $-5$ ...
15
votes
3answers
931 views

Finitely many Supreme Primes?

A challenge on codegolf.stackexchange is to find the highest "supreme" prime: http://codegolf.stackexchange.com/questions/35441/find-the-largest-prime-whose-length-sum-and-product-is-prime A supreme ...
1
vote
1answer
41 views

Need help on a proof involving the size of prime factors

Prove that the prime factors of $510510^{510510} + 1$ are greater than or equal to 19. Here is my (incomplete) proof that I need help with: 1. The prime factors of 510510 are 2, 3, 5, 7, 11, 13 and ...
0
votes
0answers
34 views

Primality of Stirling numbers of second kind

Apart from the Mersenne primes $M_p=2^p-1=\begin{Bmatrix}p+1\\2\end{Bmatrix}$, and the four primes $\begin{Bmatrix}n\\4\end{Bmatrix}$ where $n$ is given in http://oeis.org/A100958, are there other ...
1
vote
2answers
49 views

Prove that, given positive integers m and n, if m | n then 2^m − 1 | 2^n − 1. In particular, deduce that if 2^n − 1 is prime then n is prime.

I think I have the first part of the proof down but I would like to double check that my logic works: m|n $\Leftrightarrow$ n = k*m $\Rightarrow$ $2^n-1 = 2^{km}-1$ ...
2
votes
5answers
77 views

Prove that if $3\mid n^2 $ then $3\mid n $.

$n \in \mathbb{N}$ Prove that if $3\mid n^2 $ then $3\mid n $ I want to prove this in a accepted formal way, I thought about the fact that every integer can be written as multiplication of prime ...
1
vote
1answer
64 views

If n > 3 and (n + 1) is a square, is there any n that is a prime?

I am looking at properties of squares and came about this property. I am investigating the difference of squares in relation to primes.
0
votes
1answer
62 views

Is the product of adjacent primes of the form $36x^2-1$?

If $p$ and $q$ are primes such that $p-q=2$, will $pq=36x^2-1$ be always true for some natural number $x$?
14
votes
1answer
300 views

Primes as quotients

I ask this question based on a comment of David Speyer in another question. What primes are of the form $$ \frac{p^2-1}{q^2-1} $$ where $p$ and $q$ are prime? The first prime not apparently of this ...
1
vote
2answers
46 views

Prove that if $p$ is a prime and $p|k^n$, then $p^n|k^n$

I want to prove that if $p$ is a prime and $p|k^n$, then $p^n|k^n$ but I have no idea where to start.
0
votes
1answer
89 views

Proof of simple relation involving near primes?

Motivation (can skip!). (*) $\sum\log n \approx n\log n-n,$ and $$\sum\log n = \sum_{p_1\leq n} \log p_1+\sum_{p_2\leq n} \log p_2+...+\sum_{p_m\leq n} \log p_m$$ in which $p_k$ are numbers comprised ...
7
votes
8answers
4k views

Is zero a prime number?

Q: Zero is it a prime number? Q: Zero is odd or even? Q: Zero is a number? If yes or no, then why?
6
votes
2answers
60 views

Show that $\dfrac{2^p}{p}$ has remainder of $2$ for any prime $p \geq 3$

A bonus question on my last math exam I haven't been able to solve. Thanks for the help.
-5
votes
2answers
488 views

Definition of prime numbers is valid for real numbers? [closed]

Definition of prime numbers is valid for real numbers? Example: I know $1234567891 \in \mathbb N$ is prime. Then, $1.234567891 \in \mathbb R$ is also prime?
2
votes
2answers
41 views

Are there no even squares expressible as the sum of two prime squares?

When I was playing around with different number sequences, I noticed that I couldn't find any even squares that are expressible as the sum of two prime squares. Is this true, and is this related to ...
2
votes
2answers
58 views

In $\mathbb{Z}_q$ where $q$ is prime, show that $[a^q]=[a]$ for all $[a]\in \mathbb{Z}_q$

Question: In $\mathbb{Z}_q$ where $q$ is prime, show that $a^q=a$ for all $a\in \mathbb{Z}_q$. My attempt: To show $[a^q]=[a]$ for all $[a]\in \mathbb{Z}_q$, it suffices to show that for any ...
1
vote
0answers
17 views

How to split a list in n parts so the calculation time will be equal

I'm trying to implement a prime number finder. It as to find primes from 0 to X. I use this algorithm (performance may be questionable but this is not the question) to find the primes : ...
2
votes
2answers
47 views

Bases required for prime-testing with Miller-Rabin up to $2^{63}-1$

This webpage (as well as Wikipedia) explains how one can use the Miller-Rabin test to determine if a number in a particular range is prime. The size of the range determines the number of required ...
13
votes
1answer
113 views

Consequences of the negation of the Riemann hypothesis

There are many sources documenting the consequences of the Riemann hypothesis, but I can't find one discussing the consequences of its negation, particularly concerning the prime distribution. Can ...
3
votes
1answer
81 views

Why doesn't the equation have a solution in $\mathbb{Q}_2$?

I have to find for which primes $p$, the equation $x^2+y^2=3z^2$ has a rational point in $\mathbb{Q}_p$. According to my notes: Obviously, $\forall p \in \mathbb{P}, p \nmid 2 \cdot 3$, there is a ...
46
votes
3answers
4k views
4
votes
3answers
108 views

The sum of the primes, p, that satisfy the condition that $8^p+15^p$ is a perfect square.

Well, the question is so: Suppose P is the set of all primes, p, that satisfy the condition that $8^p+15^p$ is a perfect square. Find the sum of the elements of P. Now, over here, I found out a few ...
23
votes
6answers
2k 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 ...
0
votes
0answers
65 views

Rsa encryption/decryption (Updated)

1. Show that Bob can efficiently compute the encryption C(m) of the message m that he wants to send to Alice, knowing the public key but not the private key. Note: here (as well as in the rest of ...
2
votes
3answers
302 views

Infinite primes of the form 3n+2

Without recourse to Dirichlet's theorem, of course. We're going to go over the problems in class but I'd prefer to know the answer today. Let $S = \{3n+2 \in \mathbb P: n \in \mathbb N_{\ge 1}\}$ ...
12
votes
1answer
259 views

Combinatorial prime problem

Update As Barry Cipra noted in the comments, a better framing of the question might be that I'm looking at absolute differences $|a−b|$ or totals $a+b$ for $5$-smooth numbers $a$ and $b$ satisfying ...
5
votes
1answer
108 views

How many numbers are products of $p^p$?

Consider the set $\mathcal{S}=\{1,4,16,27,\ldots\}$ of numbers which are products of numbers of the form $p^p$ for $p$ prime. ($\mathcal{S}$ is A072873 in the OEIS.) Note that multiple primes are ...
1
vote
1answer
170 views

Why prime number theorem tends to one?

I am curious about prime numbers so i just started reading about it. While reading some articles i came across prime number therom (PMT) which states like this $$\displaystyle \lim_{n \to \infty} \pi ...
2
votes
1answer
55 views

Periodicity over the prime indices of a multiplicative sequence implies periodicity?

I have a real sequence $(a_p)$ indexed by the prime numbers which takes values -1, 0, or 1, having the property that $a_p=a_q$ whenever $p\equiv q \pmod m$, where $m$ is a fixed integer $>2$. I'm ...
1
vote
1answer
55 views

Find a prime number $p$ and an integer $b<p$ such that $p$ divides $b^{p−1}−1$.

Find a prime number $p$ and an integer $b<p$ such that $p$ divides $b^{p−1}−1$. First I think of long divisions but it didn't work out. Now I'm stuck..
0
votes
2answers
29 views

$\sqrt{m}$ irrational

Thinking about it, I think I found the following criterion for irrationality of $\sqrt{m}$ if $m$ is a positive integer. Let $p_1^{a_1}\cdots p_k^{a_k}$ be the prime factorization of $m$. Then ...
0
votes
1answer
19 views

Sets with no Prime Number-Generating Subsets

Are there arbitrarily large sets $S \subset \mathbb N$ such that the set $\{1\} \cup S$ has no subset that sums to a prime number?
0
votes
1answer
28 views

Function generating primes.

Is there any non-identity monotonically increasing one-one univariate function that takes prime number as input and generates prime number as output ? The asymptotic complexity to calculate output ...
0
votes
2answers
61 views

Congruence Proof Involving Fermat's Little Theorem

Let $n \in\mathbb N$. Use Fermat’s little Theorem to show that if a prime $p$ divides $n^2 + 1$, then $n^{p−1} \equiv 1 \pmod p$. So far, I have written that I need to show $n^2 \equiv -1 \pmod ...
0
votes
1answer
57 views

Combinatorial prime puzzle

Is it true that no prime larger than $241$ can be made by either acting or subtracting $2$ coprime numbers made up out of the prime factors $2,3,$ and $5?$ Update Above example is clearly wrong, as ...
-4
votes
3answers
67 views

$p$ is prime number $\implies f(p)$ is prime number. [closed]

I am in search of function $f$ that satisfies the following $f\colon \mathbb{P} \rightarrow\mathbb{P}$ and it should always satisfy the following implication. $p$ is prime $\implies f(p)$ is prime ...
0
votes
1answer
22 views

Primality Test for Safe Primes

Is this proof acceptable ? Theorem Let $N$ be of the form $N=2p +1$ with $p$ prime , then $N$ is prime iff $N \mid 2^{2p}-1$ Proof In one direction , if $2p+1$ is a prime then by Fermat ...
14
votes
0answers
289 views

Irrationality of $\displaystyle\sum_{p\in\mathbb{P}} \frac{1}{2^{p}}$

Let $\mathbb{P}$ be the set of prime numbers, and consider $m=\displaystyle\sum_{p\in\mathbb{P}} \frac{1}{2^{p}}$. Is $m$ irrational? In the following paper, the author recalls several sufficient ...
6
votes
1answer
103 views

Prime number conjecture

It was suggested that I put my full conjecture up instead of specific examples. Here it is: Given any prime p>3, there exists c such that the following conditions hold: 1a. The quadratic equation ...
0
votes
0answers
27 views

Estimate, using the Knuth-Trabb-Pardo table, how many values of $r$ would be needed in order to factor…

Use the Knuth-Trabb-Pardo table to estimate, for the original Quadratic Sieve, with all $r \ge \sqrt{n}$, approximately how many values of $r$ would be needed in order to factor a forty-digit ...
0
votes
1answer
73 views

Are there smaller orders (cardinalities) of infinity?

I am using this source as a basis for the language to ask this question. Considering the topic of degrees of infinity, are there smaller degrees than ℵ0 (aleph null, also called ω)? ...
10
votes
9answers
997 views

A Poster About Prime Numbers [closed]

We're going to design a poster about prime numbers, which will appear in a mathematics magazine for middle school students. The poster should be both visually attractive and mathematically rich. Do ...
2
votes
1answer
40 views

Irrationality of Decimal Expansion of Primes

I've heard the proof that this number is irrational is accessible to even a novice to number theory: $\alpha = 0.2 \ 3 \ 5 \ 7 \ 11 \ 13 \ 17 \ldots$ The proof may utilize that a number is ...
0
votes
1answer
56 views

A question on the prime number theorem as presented in the following paper

In the section 2. of this paper it is written that, ...The prime number theorem ensures that we can choose $B$ as close to $1$ as we want, provided $x_0$ is sufficiently large. I think that ...
1
vote
1answer
44 views

Consecutive prime numbers

Let's assume k and n are consecutive prime numbers, $k \lt n$. An axiom: for any such $k$ and $n$, $k^2 \gt n$. This seems 'obviously' true to me, but could you please prove me wrong? Or if it's ...
0
votes
0answers
32 views

Triangular number puzzle with big numbers

Let $n_T$ be the $n^{th}$ triangular number, 1+2+3+...+n or $\sum_{i=1}^n i$ , which equals ${n(n+1) \over 2}$ . Show there exists some positive integers m and c, such that the following are true: ...
1
vote
1answer
45 views

A question about the product of primes

Let $\mathbb{P}$ be the set of all primes in the natural numbers and let $p_i \in \mathbb{P}$ be the $i$th prime, $p_1=2$. Let $m = \prod_{i=1}^n (p_i)$. How many solutions does $x^2 + x \equiv 0 ...
6
votes
1answer
261 views

Showing unique prime factorization in first-order logic?

Suppose I have the symbols $\{\neg, \rightarrow, =, <,\cdot, \leftrightarrow,\land, \lor \}$ and functions $Div(x,y)$ ($x$ divides $y$), $Prime(x)$ true if $x$ is a prime, and domain $\mathbb{N}$. ...