Tagged Questions

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
27 views

Proof of Gauss formula to find number of Primes

How did gauss found this formula to find the number of primes when he was 15 , can anyone provide me the proof.
1
vote
1answer
28 views

Fermat's little theorem question

I'm studying Number theory (in my spare time) and I need to prove a lemma in order to prove the exercise. The topic is Fermat's little theorem. Well the lemma goes like this: Let's say we have ...
2
votes
1answer
44 views

On Properties of Exponentially Prime Numbers

A usual prime number is a number greater than $1$ which is not in the form of multiplication of two numbers greater than $1$. We may consider the following natural generalizations: $p>1$ is $+$ - ...
-1
votes
1answer
25 views

Prove that the sieve of Eratosthenes crosses off all composite numbers on the list but retains all the primes. [on hold]

Prove that the Sieve of Eratosthenes crosses off all composite numbers on the list but retains all the primes. I don't know where to start and how to strictly prove this statement.
6
votes
0answers
78 views

An interesting table of Prime Generating polynomials similar to $n^2+n+41$?

Here is some data on quadratic prime generating polynomials of a particular form. Kindly look at the questions given below it. $$\begin{array}{cccc} \text{#} & P(n)=an^2+bn+c\,; & d = ...
2
votes
0answers
27 views

Proof without using the proof of contradiction

By using the proof by contradiction I can determine that the root of a prime number is irrational. But how can I proof this by using the rational roots test to find rational factors of $x^n - p$. How ...
2
votes
2answers
17 views

If $n>1$ has $r$ different prime factors, then the totient is bounded by $\varphi(n) \geqslant n/2^r$?

I want to prove that if $n>1$ has $r$ different prime factors, then $$\varphi(n) \geqslant \frac{n}{2^r}.$$
0
votes
0answers
13 views

Counterexample to a generalization of Gilbreath's conjecture

Consider the arrays with "initial conditions" $L_1^1>0,\ L_{n+1}^1>L_n^1,\ L_1^{i+1}=1$ satisfying the recurrence $L_n^{i+1}\in\{L_n^i-L_{\large{\inf\{m\in\Bbb Z_{>n}:L_m^i\leq ...
0
votes
1answer
33 views

Proving $\lambda$ is the smallest one possible.

From this question , its proved that for all co-primes $a$ of $n(=pq)$ , $a^\lambda \equiv 1 \mod n$ where $\lambda= lcm (p-1,q-1)$ But how to prove that it is the smallest one possible . My ...
2
votes
1answer
29 views

Closed-form of prime zeta values

The prime zeta function is defined as $$P(s)=\sum_{p\,\in\mathrm{\mathcal P}} \frac{1}{p^s},$$ where $\mathcal P$ is the set of prime numbers. It converges for all $\Re(s)>1$. There is a related ...
0
votes
1answer
76 views

Numerical value of $\sum_{p \in \mathcal P} \frac1{p\ln p}$

In this question we determine that the series $\sum_{p \in \mathcal P} \frac1{p\ln p}$ converges, where the sum runs over primes. As I see the convergence is really slow. The partial sums for given ...
0
votes
0answers
48 views

Divisibility lattice and duality with topological spaces

Consider the integers $\mathbb{N}$ seen as a poset with divisibility as an order relation. See it as a distributive bounded lattice with gcd and lcm, with gcd being the meet and lcm the join. Clearly, ...
2
votes
1answer
70 views

$\sum_{p \in \mathcal P} \frac1{p\ln p}$ converges or diverges?

We will denote the set of prime numbers with $\mathcal P$. We know that the sum $\sum_{n=1}^{\infty}\frac1n$ and $\sum_{n=2}^{\infty}\frac1{n\ln n}$ diverges. It is also known that $\sum_{p \in ...
0
votes
0answers
26 views

Koch's version of the Riemann hypothesis for $x=p^2$

According to von Koch 1991, if the Riemann hypothesis is true, then the for the prime counting function $$\pi(x)=Li(x)+O(\sqrt x \log x)$$ For this equation, does there exist any reference or does ...
2
votes
3answers
62 views

Is this formula: $81n^2+135n+97$ wealth by prime numbers which n is natural number?

I made some effort to set a wealth quadratic formuala for prime, I found this formula: $A(n)= 81n^2+135n+97$, it gives primes for $n=0 $ to $n=18 $. I would be like some one to show me if this ...
0
votes
2answers
23 views

Proof with multinomial.

Let $p$ be a prime number. Prove that $p$ divides the multinomial $$\binom {p}{n_1,n_2,\dots, n_k}$$ such that $n_i \neq p$. I tried some approaches but honestly i have no idea what to do.
0
votes
0answers
22 views

Strong pseudoprime base b

Show that the composite number 1281 is a strong pseudoprime base 41. "$n-1=2^rm$, then n is a strong pseudoprime base b if either $b^m=1modn$ or $b^{2^sm}=-1modn$" Ok so I have $n=1281$ and $b=41$ ...
0
votes
1answer
45 views

Proof, that $a \equiv 1 \pmod{p}$

Let $n \in \mathbb{N}^{+} \smallsetminus \{{1}\}$ and $p = min\{p \in \mathbb{P} : p \mid n\}$. Also, let $a \in \mathbb{Z}$ and $a^n \equiv 1 \pmod{n}$ I need to proof, that $a \equiv 1 \pmod{p}$. ...
0
votes
0answers
38 views

How many unique combinations of sets can we get?

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 = (p-1)/2$, and ...
2
votes
3answers
38 views

Quadratic that yields the longest prime sequence?

The quadratic $n^2+n+41$ yields prime numbers all the way up to $n=40$ before it fails (pretty cool!). My question is: Do you know of a quadratic that can 'last even longer'?
0
votes
2answers
44 views

Division algorithm and Prime Numbers

In my class, the professor went through a proof that if $p|xy$ then $p|x$ or $p|y$. where p is a prime number. And now that I am reading through it, there is a small piece of the proof that I do not ...
2
votes
2answers
39 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
123 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
95 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 ...
0
votes
1answer
29 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
31 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$ ...
4
votes
1answer
33 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
61 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 ...
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 ...
4
votes
0answers
37 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 ...
2
votes
0answers
63 views

A similar, but hopefully easier problem than Gilbreath's conjecture

Gilbreath's conjecture says that for every positive integer $n$, if we write out the first $n$ primes $2,3,5,7,11,13,\ldots,p_n$ take the differences between consecutive terms ...
5
votes
1answer
151 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
24 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 ...
1
vote
0answers
41 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}$) / ...
7
votes
2answers
68 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 ...
2
votes
0answers
70 views

Prime Factor Problem To Solve

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

Is there any general method of finding the lower bound of $x$ that satisfy the inequality?

Is there any general method to find a real valued function $f(x)$ such that, $$\dfrac{x}{\ln x -(1+\epsilon)}>\pi(x)>\dfrac{x}{\ln x -(1-\epsilon)}$$ for all $x \geq f(\epsilon)$. The value of ...
2
votes
2answers
50 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
37 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 ...
1
vote
3answers
134 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" ...
1
vote
1answer
40 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 ...
3
votes
1answer
95 views

Is there any known relationship between Goldbach's comet G(n) and the prime counting function (${\pi(n)}$)?

The "extended" Goldbach conjecture defines R(n) as the number of representations of an even number n as the sum of two primes, but the approach is not related directly with ${\pi(n)}$, is there any ...
1
vote
1answer
48 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
1answer
66 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$, ...
4
votes
4answers
70 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
0answers
55 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 ...
1
vote
1answer
54 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 ...
7
votes
3answers
63 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
59 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
32 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 \}$, ...