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

0
votes
0answers
10 views

Least upper bound for $k$ such that $kp+r$ is a prime but with different binary length.

If $p$ is a prime number then is there any upper bound for $k$ (say $U$) such that $kp+r$ is also prime where $k$ is a positive integer , and $r$ is a non-negative integer lies between 0 and $p-1$ but ...
3
votes
0answers
144 views

Explicit formulas for primitive roots?

For a Fermat prime or an "upper" Sophie Germain prime a primitive root is explicitly known. Are there further results when the factorization of p-1 is known? Is it unlikely that we ever get explicit ...
1
vote
1answer
46 views

Lemma about a prime times a unit [duplicate]

I came across this Lemma: "Let $R$ be an integral domain, and let $a,u\in R$ such that $u$ is invertible. Then $a$ is a prime if and only if $au$ is a prime. I tried to prove it unsuccessfully, but ...
2
votes
2answers
40 views

Total possible combinations of primes

I have been working on a problem as follows: Do there exist 100 consecutive natural numbers none of which is prime? I know that the answer is 'yes', by considering 101!, and noting the sequence 101! + ...
12
votes
0answers
157 views

Sheldon Cooper Primes

On the $73^{\text{rd}}$ episode of the Big Bang Theory, Dr. Sheldon Cooper, an astrophysicist portrayed by Jim Parsons $(1973 - \stackrel{\text{hopefully}}{2073})$ revealed his favorite number to be ...
3
votes
2answers
103 views

Is there always a prime between $n$ and $2n$?

if we are interested to seek for the numbers of primes between $1-100$ and $100-1000$ or 1000..., why we don't asked if there is a always a prime between $n$ and $2n$ mayeb this interesting question ...
13
votes
2answers
314 views

A conjecture concerning primes and algebra

A monoid morphism $\psi:\mathbb Z_+\!\!\rightarrow\mathbb Z_+$ is defined by an arbitrary function $f:\mathbb Z_+\!\!\rightarrow\mathbb Z_+$ and defines a group homomorphism $\varphi:\mathbb ...
0
votes
1answer
32 views

Is $f(n)= \sum_{1\leq i \leq n}\log(i) - \sum_{\text{p is prime},\ p\leq n} \log(p)^2$ a function of $\operatorname{O}(n^{\frac{1}{2}+\epsilon})$?

Is $$f(n)= \sum_{1\leq i \leq n}\log(i) - \sum_{\text{p is prime},\ p\leq n} \log(p)^2$$ a function of $\operatorname{O}(n^{\frac{1}{2}+\epsilon})$? if no, what do we know about its asymptotic ...
0
votes
2answers
32 views

$R$ integral domain : $u\in R^*, a \text{ is prime} \iff au \text{ is prime}$

$R$ integral domain : $u\in R^*,\; a \text{ is prime} \iff au \text{ is prime}$ I started by looking at $auu^{-1}$. What should I do next? I'd be glad for help. Note: $u \in R^*$ meaning is $u$ ...
1
vote
0answers
49 views

Golbach's partitions: is there always one common prime in G(n) and G(n+6) , n greater or equal to 8 (or a counterexample)?

I am trying to find a counterexample for the following expression when d=6. (G(n) = Goldbach partition of the even number n) ${\forall}$ n=2*k / k${\in}$N, n${\geq}$8 ${\exists}$(${p_i}$,${p_j}$) / ...
4
votes
1answer
39 views

Proving that an ideal is prime - is it correct?

I need to prove that although $X^2 + 3X +1 \in \mathbb{Z} [X]$ is irreducible, the ideals $(5,X^2 + 3X +1 )$ and $(11, X^2 + 3X +1)$ are not prime. I know that an ideal $I$ is prime iff ...
3
votes
1answer
67 views

$p^3 + 2$ is prime if $p$ and $p^2 + 2$ are prime?

I'm self-learning number theory. I want to prove the following statement: $$p \text{ is prime } \land \text{ }p^2 + 2 \text{ is prime } \implies p^3 + 2 \text{ is prime }$$ I failed to do so, and I ...
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 ...
4
votes
0answers
41 views

Question about primes of polynomial type.

It is well known that $50$ % of the primes are of the form $x^2 + y^2$. Many variants exists where a rational amount of primes is of some integer polynomial form. But I wonder ; are there integer ...
1
vote
1answer
71 views

Is this “sliding window” unique?

Starting with $x$, which is a positive integer or zero, and $y$ a second positive integer or zero, with $y \ne x$, we can create lists. Set $p$ a prime greater than 2, $\alpha = \lfloor p/2 \rfloor$, ...
5
votes
1answer
154 views

Does this sequence of sets eventually contain all primes?

I was on Reddit earlier and answered a question about the usual proof that there are infinitely many primes: multiply any finite set of them, add 1, factor, and you get factors that are not in the ...
4
votes
1answer
27 views

Is there an $n$ such that $p|n^2+1$ with $2n<p<2n+\sqrt n$?

Is there an integer $n$ such that $n^2+1$ is divisible by a prime $p$ with $2n<p<2n+\sqrt n$? It's complicated to describe my interest, but these are near-missed for arc-cotangent reducible ...
6
votes
3answers
991 views

For any $n$, is there a prime factor of $2^n-1$ which is not a factor of $2^m-1$ for $m < n$?

Is it guaranteed that there will be some $p$ such that $p\mid2^n-1$ but $p\nmid 2^m-1$ for any $m<n$? In other words, does each $2^x-1$ introduce a new prime factor?
2
votes
0answers
75 views

Prime Factor Problem To Solve

For any positive integer $n>10$, $\lfloor \sqrt{n!}\rfloor$ has always a prime factor $> n$.
25
votes
15answers
26k views

Real world applications of prime numbers?

I am going through the problems from Project Euler and I notice a strong insistence on Primes and efficient algorithms to compute large primes efficiently. The problems are interesting per se, but I ...
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 ...
1
vote
1answer
49 views

Relation between $(a\bmod b)\bmod c$ and $a\bmod c$

Will (a%b)%c be equivalent to a%c? Given $b>c$ and $b$ is a prime number? If not is there any other equality that will hold? ...
1
vote
3answers
141 views

this is a conjecture or a result? every arithmetic progression contains a sequence of $k$ “consecutive” primes for possibly all natural numbers $k$?

writing a little better the previous question: it´s true that if we let $a$ and $b$ be coprime integers, then the arithmetic progesion : $a + bh: h\in Z$, contains a sequence of $k$ "consecutive" ...
7
votes
2answers
71 views

$\varphi(N)>\pi(N)$?

Is it trivial that $\varphi(N)>\pi(N)$ for sufficiently big integers $N$, where $\varphi$ is Euler's totient function and $\pi$ is the prime-counting function? The only exceptions less than ...
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 ...
2
votes
2answers
54 views

Primes dividing a polynomial

Let $g(x)\in \mathbb{Z}[x]$, a nonconstant polynomial. Show that the set of primes $p$ such that $p\mid g(n)$ for some $n\in \mathbb{Z}$ is infinite. I don't know how to start. I have tried asuming ...
2
votes
0answers
40 views

$x^5+a$ is reducible in $\mathbb{Z}_5[x]$ for each $a\in\mathbb{Z}_5$

Question: Show that $x^3+a$ is reducible in $\mathbb{Z}_3[x]$ for each $a\in\mathbb{Z}_3$, and that $x^5+a$ is reducible in $\mathbb{Z}_5[x]$ for each $a\in\mathbb{Z}_5$ So I got these two as my ...
2
votes
0answers
25 views

Does a random binary sequence almost always have a finite number of prime prefixes?

Does a random binary sequence almost always have a finite number of prime prefixes? Specifically, let $x = \sum_{1 \le i}{2^{-i} \cdot x_i}$ with $x_i \in \{0,1\}$ be a random real in $[0,1)$, $X_i = ...
85
votes
5answers
7k views

What is the Riemann-Zeta function?

In laymen's terms, as much as possible: What is the Riemann-Zeta function, and why does it come up so often with relation to prime numbers?
1
vote
0answers
57 views

Inequality with Euler's totient function

In A conjecture concerning primes and algebra on MSE, I defined a multiplicative function $\omega:\mathbb Z_+\!\!\to\mathbb Z_+$ with $\omega(p_n)=n$, for the $n$-th prime $p_n$. It was conjectured ...
4
votes
4answers
74 views

Find a positive integer with prime factors of at most 2, 3, 5, 7 and ends in the digits 11

Does there exist a positive integer whose prime factors include at most 2, 3, 5, and 7, and ends in the digits 11? If so find the smallest positive integer. If not, show why none exists. My professor ...
1
vote
1answer
56 views

A field between $\mathbb{Q}$ and $\mathbb{R}$ ?

I really have trouble understanding a task. We've got $p\in$ P, while P are all prime numbers. Now we construct a field $$\mathbb{Q}[\sqrt{p}]:=\{x+y\sqrt{p}:x,y \in \mathbb{Q}\}$$ The Task is to ...
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 \}$, ...
7
votes
3answers
65 views

Are there infinitely many quintuples of type $p, p + 2, p + 14, p + 26, p + 38$?

Are there infinitely many quintuples of type $p, p + 2, p + 14, p + 26, p + 38$? I think there are not... but I don't know exactly why this isn't true. My homework isn't requiring that I formally ...
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
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 ...
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 ...
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
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$ = ...
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 ...
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 ...
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 ...
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 ...
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 ...
47
votes
7answers
5k views

The myth of no prime formula?

Terence Tao claims: For instance, we have an exact formula for the $n^\text{th}$ square number – it is $n^2$ – but we do not have a (useful) exact formula for the $n^\text{th}$ ...
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
3answers
54 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 ...