3
votes
1answer
28 views

Eulers totient function divided by $n$, counting numbers in the set [1,m] that are coprime to n

If we divide Euler's totient function $\omega(n)$ by $n$, we obtain a fraction. If we multiply this fraction by any natural number $m$ which gives us another natural number $p$, is it true that $p$ is ...
-1
votes
0answers
47 views

Is the polynomial $X^{32} + 1$ irreducible? [on hold]

I think this question is interesting for Fermat number. Is this polynomial irreductible in $Z[X]$ ?
8
votes
2answers
126 views

On the difference between consecutive primes

Let $(p_n)$ be the sequence of prime numbers and $g_n = p_{n+1} - p_n$ Question: Is it known that $g_n \le n$? Remark: it's known that $g_n < p_n^{\theta}$ with $\theta = 0.525$ for $n$ ...
1
vote
1answer
25 views

Something similar to Euler's theorem

If $p$, $q$ are not equal primes. $n=pq$, $\varphi(n) = (p − 1)(q − 1)$, $d = \gcd(p − 1, q − 1)$. Is it true that for any $a$ such that $\gcd(a, n) = 1$ holds $a^{\frac{\varphi(n)}{d}} \equiv 1 ...
0
votes
1answer
49 views

Search for very large prime (greater than $2^{57885161} − 1$) between Crystal Numbers

Denote $p[i]$ as the $i$th prime. In my opinion, the following is true: Prime Gap Axiom There are always distinct prime factors for $\{p[i],p[i]+1,p[i]+2, \dots , p[i+1]\}$. Question 1 How to ...
2
votes
0answers
62 views

How prime numbers are related to special functions?

We know that the Riemann zeta function is defined as $$\zeta(s)=\sum_{n=1}^\infty\frac{1}{n^s},$$ for all $\Re(s)>1$. Because of Euler product formula we also know that $$\zeta(s) = ...
4
votes
2answers
46 views

$(n+1)^{\textrm{st}}$ prime less than $2^{2^n}$

Using elementary means, show that the $(n+1)^{\textrm{st}}$ prime is less than $2^{2^n}$ please do not use fancier stuff like the prime number theorem or beyond. using this how can you show that ...
3
votes
1answer
60 views

Convergence of infinite product of prime reciprocals?

Where pn is the nth prime number, does the infinite product $$\prod_{n=1}^{\infty}\left(1-\frac{1}{p_n}\right)$$ converge to a nonzero value? (Any help would be much appreciated!)
0
votes
1answer
28 views

Decryption of a RSA encrypted message is not working.

Using RSA with e=13 (encrypting power), d=17 (decrypting power) & n=33 (RSA modulus) I noticed that once I decrypted the encrypted message it would be different then the original message. Why is ...
0
votes
0answers
24 views

The representations of numbers by decimals

I'm looking for books that talk about the representation of the integers by decimals, more specifically for prime numbers. I can't found anything yet, I read something in "AN INTRODUCTION TO THE ...
1
vote
3answers
46 views

What makes the Mersenne primes formula more special than any of these formulas?

Mersenne Primes Formula $2^n-1$ gives false results just like any of those ones: $3^n-2, 4^n-3, P_1\cdot P_2+P_1+P_2$, or $5^n-4$ and so on.. I think that each of those formulas(including ...
1
vote
1answer
35 views

to count the intervals

A finite set of two or more consecutive natural numbers is called a "co-prime interval" if there is no number in it that is co-prime to all other numbers in the set. Given a range [A, B], I would ...
4
votes
2answers
80 views

Does there exist an $a_0$ such that the sequence $a_{n+1} = 2a_n + 1$ is prime for all $n \ge 0$?

I believe I see that $a_n = 2^n(a_0+1) - 1$ but am somewhat uncertain where to proceed afterwards. I am a complete beginner at number theory and would appreciate it if someone could point me in the ...
0
votes
2answers
50 views

Which of the following is true?

Let $\hspace{0.2cm}$$p,q,r$$\hspace{0.2cm}$ be prime numbers greater than 100,then which of the following is true? $3|p^2+q^2+r^2$ $q|p^5$ There exists integers $x,y$ such that ...
3
votes
1answer
27 views

Can we have $\sum_{n\leq [x]}e^{-\sqrt{\frac{\log x}{r}}}\ll \frac{x}{e^{c \sqrt{\log x}}}$ for some constant $c>0$, where $x>1.$

Let positive interger $n$ is square-free, that is $n=p_1p_2\cdots p_r$ some $r$. Can we have $$\sum_{n\leq [x]}e^{-\sqrt{\frac{\log x}{r}}}\ll \frac{x}{e^{c \sqrt{\log x}}}$$ for some constant ...
2
votes
1answer
34 views

If $p$ is prime and $\sigma(p^k) = n$, then $p\mid (n-1)$

If $p$ is prime and $\sigma(p^k) = n$, then $p\mid (n-1)$. proof: Suppose $\sigma(p^k) = [p^{k+1} -1]/(p-1) = n$. Then $n-1 = [p^{k+1} -1]/(p-1) - 1= [p^{k+1} -1 - (p-1)] /(p-1) = [p^{k+1} - ...
0
votes
3answers
32 views

Canonical decompositions and product of primes

Let $S$ be the set of natural numbers $n$ that have exactly $9$ positive divisors. Describe all possible canonical decompositions (as products of primes) of elements of $S$.
0
votes
0answers
58 views

Prime Reflections

How would you describe the following pattern?: For each primorial from 30 onward, there exists a pattern in the arrangement of the prime factors of the composite numbers which I call "the mirror ...
2
votes
2answers
78 views

Can Andrica's conjecture be proven by proving a tighter upper bound for prime gaps?

I checked some differences between square roots of various natural numbers and I am wondering what is required to prove Andrica's conjecture. Would a tighter upper bound for the prime gap above $n$ be ...
1
vote
0answers
30 views

The Existence of “Simple” Prime Generating Functions

Obviously, we do not know an explicit and easily manipulable formula for finding every prime - that is, a function $f(n)$ which yields the $n^{th}$ prime. I've seen plenty of formulas that "cheat" in ...
1
vote
0answers
10 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 = ...
3
votes
2answers
109 views

The Conjecture That There Is Always a Prime Between $n$ and $n+C\log^2n$

Let $n$ be 113. Use $n+C\log^2n$ to find the next consecutive prime or at least approximately how far away it is. Will you show me how to work this out step by step to show me how to use this formula? ...
1
vote
3answers
55 views

Finding if a number is prime by looking at the sum of their digits

Take a number $N = \overline{abcdef...}$ where $a, b, c, d,e,\dots$ are the digits of $N$. Let $k$ be the sum of those digits : $a+b+c+d+e+... = k$ If $k$ is any of ${1, 2, 4, 5, 7, 8 }$ then $N$ ...
2
votes
1answer
61 views

Closed form for $\sum_1^\infty 1/p^n$

I was wondering if there are some studies on closed forms for the sum $$\sum_{p \in \mathbb{P}}^\infty \frac{1}{p^n},$$ where $\mathbb{P}$ denotes the set of prime numbers. Obviously I know that ...
0
votes
2answers
35 views

The Greatest Prime Less Than $n$

Let $n$ be any natural number greater than 2. Let $l$ be the greatest prime less than $n$. When $n$=3, $l$=2. When $n$=10, $l$=7. When $n$=25, $l$=23. What is the relationship between $n$ and $l$? ...
0
votes
1answer
43 views

Exact Equivalence of Legendre's Conjecture Impossible?

If the upper bound for the prime gap above $n$ is such that $n$+4$\sqrt{n-1}$$\geq p$, where $n$ is any given natural number and $p$ is the next prime after $n$, then Legendre's conjecture is true. If ...
0
votes
1answer
95 views

Gaps between primes: bounds - a question of possibilty [closed]

Let $n$ be any given natural number. Let $p$ be the very next prime greater than $n$. Let $b$ be the bound for the prime gap above $n$. Here, the bound is strictly the limit from $n$ to $p$, meaning ...
0
votes
1answer
16 views

Bounded by a constant?

What exactly is meant by "constant" when it is said that Legendre's conjecture implies that the upper bound on the prime gap above n could be bounded by the product of a constant and the square root ...
1
vote
1answer
91 views

Primes of the form $x^2+ny^2$

The problem of the characterization of primes of the form $p=x^2+ny^2$ is solved (e.g. in the book of Cox), and there are also a few examples for special numbers $n$. My question is: Does anyone ...
13
votes
3answers
496 views

Calling all genius: $p_1^{e_1} p_2^{e_2}…p_k^{e_k}=e_1^{p_1} e_2^{p_2}…e_k^{p_k}$

Find all positive integer $e_i$ and prime number $p_1^{e_1} p_2^{e_2}...p_k^{e_k}=e_1^{p_1} e_2^{p_2}...e_k^{p_k}$ for $k\ge 1$. Is this impossible or what? I've been trying for at least a week. I've ...
5
votes
0answers
121 views

Does this prime generating way generate all the prime numbers?

I've thought of the following algorithm to find the entire list of prime numbers: Take a prime number $p$ to your list. $1.$ Multiply all the numbers in your list and call the number you get ...
3
votes
3answers
84 views

Are there infinitly many primes of the form $n!+1$?

For some numbers $n!+1$ is prime, but all such numbers are not prime. For example, $5!+1 = 11\times 11$. The question is this: Are there infinitely many primes of the form $n!+1$?
1
vote
1answer
50 views

A question concerning a lower bound of $\pi (n)$

In the number theory course, I was asked to prove the following: $$2^{\pi(n)} \sqrt{n} > n \mathrm{\, for\, all\, } n > 1 \in \mathbb{N}$$, where $\pi(n)$ denotes the number of prime number ...
1
vote
2answers
64 views

proportion of primes in a polynomial sequence

It is conjectured (Bunyakovsky) that when $P(x)$ is a polynomial from $\mathbb{Z}[X]$, irreducible, with positive leading coefficient and so that the integers $P(n)$ , $n\gt0$ do not share a common ...
0
votes
2answers
55 views

Why does not the perfect number formula imply there are infinitely many perfect numbers?

We know the even perfect number formula is $2^{p-1}(2^p − 1)$ and it is known that the multiplication of a even number and odd number is a even number. So why can't we say there are infinitely many ...
1
vote
1answer
44 views

No. of solutions of two equations?

What is the number of distinct primes $p$ such that $$\binom{\frac{p+1}2}2\ =\ 5\cdot r\cdot q$$ where $5<r<q<p$ are primes. (See the answer given by avz2611 in the following). Similarly, if ...
4
votes
2answers
137 views

Is this statement equivalent to Legendre's conjecture?

The maximum distance from any given number n to the next prime is less than twice the square root of n. Is this statement equivalent to Legendre's conjecture? Is this statement worded correctly? If ...
-2
votes
2answers
27 views

Prove that for a prime number $p$ and an arbitrary natural number n$\ge$ 1 it holds that gcd(p,n) is either equal to 1 or to p. [closed]

Prove that for a prime number $p$ and an arbitrary natural number n$\ge$ 1 it holds that gcd$(p,n)$ is either equal to 1 or to $p$. i just dont know where to start with this proof, it is a homework ...
3
votes
1answer
60 views

If $n-1$ is $f(n)$-smooth, $n$ is prime infinitely often. What is the best $f$?

If $n-1$ is $f(n)$-smooth, $n$ is prime infinitely often. What is the best $f$? For all primes $p$, $p-1$ is $\frac{p}{2}$-smooth, so $f(n) = \frac{n}{2}$ works. If $q$ is a Fermat prime, then ...
3
votes
0answers
81 views

A question on the Prime number theorem

Let $N\geq1$. Could we infer $$\sum_{n\leq N}\mu(n)\ll N\exp(-c\sqrt{\log N})$$from $$\sum_{n\leq N}\Lambda(n)= N+O(N\exp( -c\sqrt{\log N})$$or $$\sum_{p \leq N}1=Li(x)$$ without resorting to the ...
10
votes
2answers
271 views

Is there any infinite set of primes for which membership can be decided quickly?

The AKS algorithm decides whether or not $n$ is prime in time $\tilde{O}((\log{n})^6)$. I am wondering if there is any faster algorithm to determine membership in some infinite set of primes. What I ...
3
votes
1answer
72 views

Does there exist a finite set of polynomials which do not have roots over any prime field?

The polynomial $x^2 + 1$ has a root in $Z_p$ if and only if $p \not\equiv 3 \mod 4$, and the polynomial $x^2 + x + 1$ has a root in $Z_p$ if and only if $p \not\equiv 2 \mod 3$. So each of the ...
45
votes
6answers
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}$ ...
0
votes
1answer
30 views

Proving an inequality on the sum of $\log$ of primes.

Let $S(x)=\sum_{p\leq x} \ln(p)$ where $\sum_{p\leq x}$ denotes a summation over the positive prime numbers that are $\leq x$ Prove that $\forall n \in \mathbb N, S(2n+1)-S(n+1)\leq ...
0
votes
0answers
52 views

Upper bound number of distinct prime factors

I want to prove that if $\omega (n)$ is the number of distinct prime factors of $n$ for $n>2$ we have $\omega (n) \leq \frac{\ln n}{\ln \ln n} + O(\frac{\ln n}{(\ln \ln n)^2})$. How can I do this? ...
0
votes
0answers
54 views

Relation between Galois theory and Fermat primes

I am curious about a possible relation between Galois theory and Fermat primes. There is a general solution to any polynomial equation of degree less than or equal to $4$. The only Fermat primes (of ...
0
votes
1answer
62 views

Prime number theorem lemma: prove that $\psi(x)\sim\pi(x)\log(x)$

I'm trying to follow the proof in Wikipedia that the PNT is equivalent to the assertion $\psi(x)\sim x$, by proving that $\psi(x)\sim\pi(x)\log x$, which it claims is a very simple proof. One ...
0
votes
1answer
39 views

Length in time to find the longest range of primes between 2 and a 13 million character digit?

I am trying to run a program that tells me how many prime numbers there are in a range of numbers. I run it in intervals of 10,000 to 100,000. How long would the program take to determine all the ...
1
vote
0answers
40 views

Prime numbers that fits in a specific pattern

Any series $\displaystyle \sum_{k=0}^{\infty}a_k2^{-k}$, where $a_k\in\{0,1\}$, converges to some $x\in[0,2]$ and since the sequence $a_n$ is unique for each $x\in[0,2]$ there is an bijection between ...
0
votes
1answer
30 views

Minimal distance between coprimes

For a natural number $K$, I want to choose $n$ pairwise coprime numbers all of which are bigger than $K$ such that the distance $d$ between the smallest and the largest one is minimal. For example, ...