Questions tagged [prime-numbers]

Prime numbers are natural numbers greater than 1 not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

Filter by
Sorted by
Tagged with
4
votes
2answers
107 views

If $f$ and $g$ are nonzero polynomials with $\deg f>\deg g$, and if $pf+g$ has a rational root for infinitely-many primes $p$, then …

An IMO shortlist polynomial problem: Let $f$ and $g$ be two nonzero polynomials with integer coefficients and $\deg f>\deg g$. Suppose that for infinitely many primes $p$ the polynomial $pf+g$ has ...
3
votes
1answer
61 views

Primality test for specific class of $N=k \cdot 2^n+1$

Can you prove or disprove the following claim: Let $N=k \cdot 2^n+1$ be a natural number that is not a perfect square such that $ 2 \nmid k$ , $n>2$ . Let $c$ be the smallest odd prime number such ...
12
votes
3answers
966 views

Where can I find the modern proof of the prime number theorem?

Terence Tao described a modern proof of the prime number theorem in a lecture in UCLA, which is stated in wiki(enter link description here). From wiki: In a lecture on prime numbers for a general ...
5
votes
1answer
75 views

Verify my proof that for any $n>1$, if $n^n+1$ is prime, then $n=2^{2^k}$ for some integer $k$.

I am solving a problem and I am respectfully asking someone to critique my work and offer suggestions on formatting or point out any glaring logical errors. Here is the problem: Prove that for any $n&...
4
votes
0answers
170 views

Can the inverse of the Riemann zeta function in $s > 1$ be expressed as a series?

In this post, we are interested in the Rimenann zeta function $\zeta(s)$ in $s > 1$ only where it is strictly decreasing rather than $s$ in the entire complex plane. We have the Stieltjes series ...
3
votes
1answer
1k views

Super palindromes

Can anybody be kind enough to explain what exactly is a super palindrome? Also consider the following example : $923456781-123456789=799999992:9=88888888$ The largest prime factor of $88888888$ is ...
1
vote
1answer
90 views

Is there another palindrome-Carmichael-number?

$$101101$$ is a cute number indeed. It is the smallest palindrome-Carmichael-number. Furthermore, its square and its cube are also palindrome! And it is a "binary" number containing only the digits $0$...
46
votes
1answer
2k views

Pattern “inside” prime numbers

Update $(2020)$ I've observed a possible characterization and a possible parametrization of the pattern, and I've additionally rewritten the entire post with more details and better definitions. It ...
5
votes
2answers
689 views

Is there any guarantee of maximum distance to next prime?

When watching the Numberphile video about Highly Composite Number, I spotted something that aroused some of my doubts. One of properties suggested by Ramanujan was that the highly composite number's ...
0
votes
1answer
24 views

Indicator equation $f(n) = n$ for $n \in \Bbb{N}$ such that $n \pm 1$ is a pair of twin primes.

Consider the formula: $$ f : \Bbb{N} \to \Bbb{C} \\ f(n) := 2 + \sum_{a = 1}^{n-2} \exp\left({\dfrac{2\pi i}{\gcd(a, n^2-1)}}\right) $$ If $n \pm 1$ is a pair of twin primes, then $f(n) = n$. This is ...
8
votes
2answers
127 views

Convergence of $\sum_{p>2} \frac{(-1)^{\frac{p-1}{2}}}{p}$

Consider the sum $\sum_{p>2} \frac{(-1)^{\frac{p-1}{2}}}{p}$ where $p$ runs only through all odd primes. Show that this sum converges. The possibly best approach I have until now is via Partial ...
3
votes
3answers
5k views

Formula for composite numbers

I was digging around blogspot when I came upon an old post that claimed the author discovered a formula that generates all odd composite numbers. The post: http://barkerhugh.blogspot.com/2012/05/...
1
vote
1answer
58 views

What is the chance that a number $P$ is prime if it's not divisible by any number less than $x$?

I am trying to check if a very big number ($>10^{10,000,000}$) is possibly prime. I have written a computer program to check if the number has any smallish (less than like $600,000,000$) factors......
2
votes
0answers
70 views

Irrationality of $(p_1 + p_2)/(p_1 \times p_2) + (p_1 + p_2 + p_3)/(p_1 \times p_2 \times p_3) + \ldots$, where $p_i$ is an $i$-th prime

Assuming that $p_i$ denotes an $i$-th prime, the number $x$ is defined as follows: $$\begin{array}{l} x = \frac{{{p_1} + {p_2}}}{{{p_1} \times {p_2}}} + \frac{{{p_1} + {p_2} + {p_3}}}{{{p_1} \times {...
168
votes
6answers
27k views

Deleting any digit yields a prime… is there a name for this?

My son likes his grilled cheese sandwich cut into various numbers, the number depends on his mood. His mother won't indulge his requests, but I often will. Here is the day he wanted 100: But ...
2
votes
2answers
69 views

There is a prime between $n$ and $n!-1$ [duplicate]

One way to show that there are infinitely many primes is to show that for $\forall n \ge 3$, there is a prime p such that $n \lt p \le n!-1.$ I thought of assuming that the numbers in the sequence $n+...
3
votes
1answer
840 views

Prime Triangle:: How to find the position(row and column) of prime number in a triangular arrangement

I was working on problem which asks the position of a prime number in a triangular arrangement. If we arrange the all prime up to $10^8$ as shown in image we can find the row and column number of a ...
94
votes
1answer
2k views

Can we remove any prime number with this strange process?

This is a little algorithm I made today, which may appear to be quite complex, so I will start with an example. Questions are at the end of the post. The process goes as follows: Start with the first ...
26
votes
2answers
10k views

Probability that two random numbers are coprime is $\frac{6}{\pi^2}$

This is a really natural question for which I know a stunning solution. So I admit I have a solution, however I would like to see if anybody will come up with something different. The question is ...
4
votes
1answer
47 views

Reasoning about a sequence of consecutive integers and factorials with hope of relating factorials to primorials

I am looking for someone to either point out a mistake or help me to improve the argument in terms of clarity, conciseness, and more standard mathematical argument. Let $x$ be an integer such that $x,...
4
votes
2answers
106 views

Show that $\pi(n) \geq \log_2\log_2 2n$

Doing some excercise on elementary number theory I have proved that for every $n \in \Bbb{N}, p_{n+1} \leq p_1p_2...p_n + 1$, based on this result I'm also was able to prove that for every $n \in \Bbb{...
2
votes
0answers
48 views

What is the smallest product, $m$, of $6$ distinct odd primes such that $\frac{d+\frac{m}{d}}{2}$ is prime for all $d$ dividing $m$?

I am currently working on a sequence, $a_n$, that is defined as follows: $$a_n\text{ is the smallest product of }n\text{ distinct odd primes, }m=p_1p_2\dots p_n\text{, such that }\frac{d+\frac{m}{d}}{...
3
votes
1answer
233 views

Using CRT to find arbitrarily long gaps between primes

It is straight forward to find a gap between primes that consists of at least $2n$ using only the Chinese Remainder Theorem. Let $p_n$ be the $n$th prime. Find $x$ such that: $$x \equiv -1 \pmod 2$$...
-4
votes
1answer
51 views

Finding pattern for prime numbers [closed]

I was trying to find pattern for prime numbers. I find applying $\sin(\frac{x}{p})$ where $p$ is prime number, acts as applying sieve. Then I formulated a function: $y=\sin(x)\csc(\frac{x}{2})\csc(\...
8
votes
2answers
118 views

Does $\Phi_n(\alpha)=0$ in $\Bbb{F}_p$ for some $\alpha\in\mathbb{F}_p$ imply that $\mathrm{ord}(\alpha) = n$?

Let $\Phi_n(x)$ denote the $n^\text{th}$ cyclotomic polynomial. Suppose it has a root $\alpha$ in the finite field $\Bbb{F}_p$ and $p \nmid n$. Does it follow that $\mathrm{ord}(\alpha) = n$? In the ...
58
votes
2answers
3k views

Why are the last two numbers of this sequence never prime?

I had the idea to make a script that generates a pattern like this: 1 2 3 4 5 6 7 8 9 10 ... and so on. After that, I replaced every non-prime by a '-' ...
4
votes
1answer
152 views

A mysterious prime number 127

127 is probably the LAST / LARGEST prime number p such that $p^2$ mod q has an odd residue, where q is the previous prime number right before p. I have checked it up to $10^6$ , and it turned out to ...
0
votes
1answer
22 views

Asymptotic lower bound for the prime counting function, $\pi(x)?$

Consider a function that attempts to count primes up to a given $x$:$$\varphi(x)=\int_2^x \frac{1}{\log(t)}e^{-\frac{1}{\sqrt{t}}}~dt$$ Is $\varphi(x)$ an asymptotic lower bound to the prime counting ...
6
votes
1answer
114 views

Prime numbers which divide $n^3-3n+1$

Let $f(n)=n^3-3n+1$. It can be proved that for any prime $p$ and integer $n$ such that $p\mid f(n)$ we have either $p=3$ or $p\equiv\pm1\pmod 9$ (see below). Indeed, suppose that for prime number $p$ ...
3
votes
0answers
113 views

Is $N=2^{2^n}+2^{2^{n-1}}+2^{2^{n-2}}+2^{2^{n-3}} + \ldots+ 2^{2^3}+2^{2^2}+n$ is always composite?

Is number of the following form is always composite: $$N=2^{2^n}+2^{2^{n-1}}+2^{2^{n-2}}+2^{2^{n-3}} + . . . 2^{2^3}+2^{2^2}+n$$ I found similar question for $2^{2^n}+5$ . My attempt: We can rewrite N ...
1
vote
1answer
270 views

Conjectured compositeness tests for $N=k\cdot b^n \pm c$

How to prove that these conjectures are true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ ...
2
votes
0answers
86 views

Is there a name for this family of sequences?

The sequence ${\displaystyle{M_n:=2^{p_n}-1}}$, where ${\displaystyle{n\gt0}}$ and ${p_n}$ is the ${\displaystyle{n}^{th}}$ prime number, is commonly known as the Mersenne numbers (not to be confused ...
-2
votes
0answers
78 views

Every prime = $2$ some prime + (1 or another prime)

I have a conjecture I wish to prove. Every prime number is the sum of twice one prime + another prime. In other words, if $\mathscr{P} = \text{Primes} \cup \{1\}$, $$\forall A >2 \in \mathscr{P},\...
0
votes
1answer
118 views

What is the Explicit Formula for $\log(\zeta(s))$?

The explicit formula for the logarithmic derivative $\frac{\zeta'(s)}{\zeta(s)}$ is illustrated in (1) below. (1) $\quad\frac{\zeta'(s)}{\zeta(s)}=\frac{s}{1-s}+\log(2\,\pi)-\frac{1}{2}H_{\frac{s}{2}}...
0
votes
1answer
89 views

If $\Delta O \pmod {2^n} = (2)$ in $\Bbb{Z}/2^n$ for all $n \geq 1$, then does $\Delta O = (2)$ in $\Bbb{Z}$?

Let $O = $ the set of odd primes in $\Bbb{N}$. And $M = \Delta O = \{ x-y: x,y \in O\}$. Then we can take either set $X$ modulo $n$ for any $n \geq 2$: $\overline{X} = \{ x + (n) : x \in X\}$. Then ...
1
vote
1answer
41 views

Is $\gcd(p_1^{n_1},\cdots,p_k^{n_k})=1$ if each $p_i$ is a prime number?

Is $\gcd(p_1^{n_1},\dots,p_k^{n_k})=1$ if each $p_i$ is a prime number and $n_i\geq0$? I just really want to know if it is the case or not, I am not really intersted in a proof. Also, if this is the ...
2
votes
1answer
38 views

How many rational numbers $m/n$ are possible under given conditions?

Find the number of rational numbers $m/n$, where $m,n$ are relatively prime positive integers satisfying $m<n$ and $mn=25!$. My Approach: Let $25!=2^{a_1}3^{a_2}5^{a_3}\ldots19^{a_8}23^{a_9}$ Now $\...
0
votes
2answers
119 views

Demonstrating that a number x is the smallest such that 24x (mod 59) ≡ 2 (mod 59)

I have to find a number x such that x is the smallest natural number that satisfies this equation: $24x (\mod 59) = 2(\mod59)$. Using Fermat's little theorem and Euler's primes function, given that ...
2
votes
1answer
81 views

Let $ a$ be a fixed natural number. Prove that the set of prime divisors of $ 2^{2^{n}} + a$ for $ n = 1,2,\cdots$ is infinite

$\textbf{Question:}$Let $ a$ be a fixed natural number. Prove that the set of prime divisors of $ 2^{2^{n}} + a$ for $ n = 1,2,\cdots$ is infinite. I have come to know that this problem easily follows ...
1
vote
1answer
39 views

$\Bbb{Z}$-module of subsets of $\Bbb{Z}$ with elementwise scalar multiplication and subset symmetric difference addition.

Consider the elementwise product $A\cdot B = \{ ab: a\in A, b \in B\}$ and let $A \Delta B = (A \setminus B) \uplus (B \setminus A)$ be the symmetric difference of subsets of $\Bbb{Z}$. We know that ...
4
votes
1answer
11k views

ALL Prime Numbers Within 2 Columns of Number Pyramid - Proof?

I was arranging numbers putting them in different orders when I happened to build a pyramid and noticed that two columns of the pyramid seemed to contain all of the prime numbers. Not just some of ...
0
votes
1answer
49 views

Can the mean of 2 consecutive prime numbers be prime?

This is apparently a "hard" question, and I don't know if I'm missing something, but it seems trivial to me. Aside from 2, all other prime numbers are odd. So the mean of any consecutive ...
2
votes
1answer
42 views

Approximating $\vartheta(x)=\sum_{p\le x} \log(p)?$

Consider the first Chebyshev function $\vartheta(x)=\sum_{p\le x} \log(p)$ where the sum runs over the primes less than or equal to $x$. I wanted to approximate $\vartheta(x).$ My attempt was $f(x)=\...
2
votes
5answers
114 views

What is a quick way (without calculator) to determine that $(2^9 + 1)^2 + 2^9 + 2$ is not prime?

I came across the following expression $(2^9 + 1)^2 + 2^9 + 2$, which is divisible by 7 and thus not prime. Without this information and a calculator, how could I easily determine that this number is ...
1
vote
3answers
85 views

Solving $n^{15} \equiv p - 1 \space \pmod p$ for $n \in [1 , L]$

For a given prime $p$, and an upper limit $L$ of integers that I am interested in, I am trying to find all values of $n$ in the range $[1,L]$ for which the following equation holds: $$n^{15} \equiv p -...
1
vote
3answers
69 views

Fermat's theorem on sums of two squares (every prime $p$ s.t. $p \not\equiv 3 \pmod 4$ is a sum of two squares)

I'm reflecting the following proof (see below). My question is where it uses the given fact ($p \not\equiv 3 \pmod 4$)? I'm not sure it uses this fact, and it kind of makes me think that something is ...
1
vote
0answers
76 views

Is there a known formula for the number of $k^{\text{th}}$ power residues modulo $2^n$?

We define a $k^{\text{th}}$ power residue modulo $n$ to be an integer $a$ coprime to $n$ such that there exists an integer $x$ satisfying $$x^k\equiv a\pmod{n}.$$ A fundamental question that we can ...
3
votes
2answers
94 views

A motivating argument for studying determinants of $2\times 2$ matrices with prime entries in relation to Goldbach's conjecture.

Let $\Bbb{P}$ be the set of odd primes. Let $X_n$ for $n \geq 3$ be the Goldbach solution set $X_n = \{(p,q) \in \Bbb{P}\times \Bbb{P} : 2n = p + q \}$. Suppose that for combinatorial reasons we are ...
30
votes
0answers
3k views

Towards a new proof of infinitude of primes ( with possible unified application to other primes of special forms whose Infinitude is unknown):

I'm trying to prove the infinitude of primes as follows: Consider the following partial sum : $$S(p)=\sum_{n=2}^p\sin^2\left(\frac{π\Gamma(n)}{2n}\right)$$ The summand is zero for non-primes greater ...
2
votes
1answer
32 views

$\sum_{p,m\geq 3}(-1)^{m(p-1)/2}e^{-p^my}\log p = O(y^{-1/3})$

Show that for sufficiently small $y$ we have $\sum_{p,m\geq 3}(-1)^{m(p-1)/2}e^{-p^my}\log p = O(y^{-1/3})$ where $m\geq 3$ represents all positive integers from $3$ onwards, while $p\geq 3$ ...