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

3
votes
1answer
64 views

Find a sequence of 7 consecutive primes

Find a sequence of 7 consecutive primes. So these primes have to have the same "gap" in between them. So far I have been doing this in a brute force way, by looking a ta list of all the primes and ...
1
vote
1answer
38 views

Prove the identity in Ring of Integers Modulo Prime

I have many study tasks, but I do not have any example. Therefore, I do not know, how to solve these tasks. For example, I need prove, that: $\{ b \in \mathbb{Z}_{p^n} \mid b^2 =1\} = \{-1, 1 \}$, ...
3
votes
1answer
39 views

Euclid's lemma for non-prime numbers.

I was trying to prove that $\sqrt{6}$ irrational as: Let $$\sqrt{6}=\dfrac ab$$ $$\implies a^2=6b^2$$ $$6|a^2 \implies 6|a$$. I should not be able to do the step because 6 is not a ...
4
votes
1answer
38 views

Existence of primes $q$ such that $p\mid q-1$ and $q\mid p^n-1$

Let $p$ be a prime. By Dirichlet's theorem on arithmetic progressions, there are infinitely many primes $q$ such that $p\mid q-1$. Must there be also primes $q$ such that $p\mid q-1$, and also, $q ...
0
votes
0answers
9 views

GRAM series and Logarithmic integral

due to the prime number theorem wouldn't we expect that the prime number counting function admits the approxiamtion $$ \pi (x)= \gamma +loglog(x)+ \sum_{n=1}^{\infty} \frac{log^{n}(x)}{n.n!.\zeta ...
1
vote
1answer
40 views

Prime factorization difficulty

From Wikipedia: Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are semiprimes, the product of two prime ...
0
votes
2answers
53 views

Show there is no solution to this equation

I have to show that $2x^4-20x+8$ cannot be divided by $16$ without remainder. The only thing comes to my mind is to write $16$ as $4^2$ which hasn't been of any help. Could you give me some hints to ...
1
vote
0answers
42 views

Proving multiplicative property of euler's totient function $\phi$ using probability

If $m,n$ are co-prime , we know that $\phi(mn)=\phi(m)\phi(n)$. I want to prove it using probability. Probability that a selected number less than or equal to $mn$ is co-prime to $mn$ = ...
3
votes
2answers
86 views

Prime elements in the gaussian integers

Prove: If a prime number $p\in \mathbb N$ is from the form $p=4k+3,k\in \mathbb N$, then its also a prime number in $\mathbb Z[i]$,i.e. if $p|(z_1\cdot z_2)$ then $p|z_1$ or $p|z_2$. I dont have any ...
2
votes
2answers
90 views

Idea for primality testing based on a trigonometric product

This is an idea that I had about 3 months ago. I tried some college professors, they didn't care. I tried to solve, but with no luck. I ask for help to find the closed form of the following product ...
3
votes
0answers
67 views

Question about application of Erdős-Kac theorem

My question is whether (*) below can be shown using the Erdős-Kac theorem? I don't think the distinction between $\Omega$ and $\omega$ is important here. For lack of better notation let ...
4
votes
3answers
148 views

Is there a real number $r$ such that $\sum\limits_{k=0}^{\infty}\frac{p_k}{r^k}=e$?

Let $p_n$ denote the sequence of prime numbers, with $p_0=2$. I'm looking for a real number $r$ such that $\sum\limits_{k=0}^{\infty}\frac{p_k}{r^k}=e$. It's easy to show that $r>5$, with ...
2
votes
1answer
83 views

Corollaries of Green-Tao Theorem?

there is already a good thread which discusses some corollaries of the Green-Tao Theorem, here: Constructing arithmetic progressions The question I was wondering about is of a similar flavor but ...
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 ...
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
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
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$ ...
0
votes
0answers
11 views

Let $g_n^k=p_{n+k}-p_n$, where $p_n$ is the $n$th prime. Does there exist $g_{k+1}^1=2$ such that $g_1^k,g_2^k,\ldots$ is a “Gilbreath sequence?”

Call $(S_i)_{i=1}^{\infty}$ a Gilbreath sequence if $1=\lvert S_2-S_1\rvert=\lvert \lvert S_3-S_2\rvert-\lvert S_2-S_1\rvert\rvert=\cdots$, i.e., if the sequence can be substituted for the primes in ...
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$ ...
1
vote
0answers
65 views

Primality of Stirling numbers of second kind (again)

This question follows a previous one on the primality of Stirling numbers of the second kind ${n \brace k}$. Gerry indicated a paper on the topic. In this paper it is shown that for ${n \brace k}$ to ...
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 ...
2
votes
0answers
78 views

Humankind knows the prime factorization of the first how many consecutive integers?

I am only looking for an approximation. I'm guessing the answer must be somewhere between $10^{20}$ and $10^{50}$. . Edit: Okay so my first initial estimation was pretty poor... I should have ...
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$?
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.
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
0answers
65 views

Test: Total number of twin primes in the vicinity of twin primes: how can I calculate the upper and lower bounds of the results?

I have performed the following test, and according to the results, I do not know how to define a function to calculate the limit of the lower and upper bounds of the data results. Besides, looking at ...
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.
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 ...
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 ...
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
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}\}$ ...
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 ...
46
votes
3answers
4k views

Do we have negative prime numbers?

Do we have negative prime numbers? $..., -7, -5, -3, -2, ...$
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
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 ...
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 ...
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 ...
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 ...
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 ω)? ...
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
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 ...