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

1
vote
1answer
45 views

On an exercise from a journal using Hölder and Stoltz theorems, now with twin primes

I use [1] (in spanish) for the sequence of positive terms defined by $$ a_k = \begin{cases} \frac{1}{k}(\frac{1}{p_k}+\frac{1}{p_k+2}), & \text{for the kth twin prime pair} \\ 0, & \text{if ...
2
votes
1answer
70 views

A conjecture about the prime counting function

Using this lemma it can be proved that $\Delta(m,n)=\pi(m\cdot n)-\pi(m)\cdot\pi(n)+1$ (where $\pi$ is the prime counting function) is a function $\Delta:\mathbb N\times\mathbb N\to\mathbb N$. ...
2
votes
0answers
26 views

The nth roots of $z_n=p_n\cdot(i)^{p_n}$, where $i=\sqrt{-1}$ and $p_n$ is the nth prime number

I want refresh some basics too in Complex Analysis. Let $p_n$ the sequence of prime numbers $2, 3, 5, 7\ldots$, thus $p_n$ is the general term of this sequence, and $i=\sqrt{-1}$ is the complex ...
-5
votes
1answer
107 views

Twin prime conjecture hypothesis

Let $c$ be a positive integer and fix $a=c-1$, and $b=c+1$. Challenge: Find the largest value of $c$ such that $ac\pm1$ and $bc\pm1$ are pairs of twin primes. For example, with $c=6$ we have ...
4
votes
1answer
60 views

Proving for $n \ge 25$, $p_n > 3.75n$ where $p_n$ is the $n$th prime.

The elements of the reduced residue system modulo $30$ are $\{1, 7, 11, 13, 17, 19, 23, 29\}$ If we order them as $e_1, e_2, e_3, \dots$ so that $e_1 = 1, e_2 = 7, \dots$, it follows that $3.75(i-1) ...
4
votes
2answers
130 views

Infinite product involving primes

I just had my first analysis course as an undergraduate, and I'm trying to learn more about analytic number theory. Right now I'm looking at prime numbers in particular--I'm studying (mostly just ...
2
votes
1answer
34 views

Periodicity of fractional part of a sequence

Let $u_n = \mathrm{frac}(a n^2)$, where $a$ is some real number and $\mathrm{frac}$ denotes the fractional part. Question 1) Can $u_n$ be eventually periodic even if $a$ is irrational? Question ...
2
votes
2answers
38 views

Prove that $\sigma(n)\le \lceil\log_2(n)\rceil$

Let $f:\mathbb{N}\to\mathbb{N}$ be defined as $f(1)=1$ and if $n=\prod_{r=1}^{k}p_r^{\alpha_r}$ is the prime decomposition of $n$ then: $$ f\left(n\right)=\prod_{r=1}^{k}(p_r-1)^{\alpha_r} $$ Let ...
0
votes
3answers
48 views

Generate prime of x decimal digits using bit-oriented prime generator

I've got a question on stackoverflow where somebody asks to generate a random 18-digit prime. Unfortunately, the only prime generator is the one from OpenSSL. This prime generator is however geared ...
4
votes
1answer
44 views

Weak form of Dirichlet's theorem.

Dirichlet's Theorem on arithmetic progressions is often stated as something like: Every arithmetic progression where the first term and the difference are coprime contains an infinite amount of ...
0
votes
1answer
42 views

Get from prime number theorem to the approximate equality of nth prime to n*logn

I saw in my textbook the following theorem: $\pi(n)\sim n⁄ \log n$ And it states the following corollary from this theorem: $p_n\sim n \log n$ I tried to think how they made that conclusion but to ...
1
vote
5answers
72 views

Proof that $2^{2n}-1$ is not prime for $n \in \mathbb{N}, n > 1$

I notice that the number seems to be a multiple of 3: for n=2: $2^4 -1 = 15 $ for n=3: $2^6 -1 = 63$ for n=4: $2^8 -1 = 255$ How do I generalise?
3
votes
2answers
91 views

Squeezing primes

Any positive odd number $n$ can be coded one binary digit smaller by the rule $\frac{n-1}{2}$ and that's obviously the best squeeze: a bijection from $\mathbb N$ such that $f(n)\geq n$. I'm looking ...
0
votes
3answers
147 views

Prove that 2016 cannot be expressed as sum of prime and triangular number

As in the title. I've read that 2016 cannot be expressed in such form, but I've completely no idea, how could this fact be proven.
1
vote
1answer
25 views

Density of primes of the form $kn\pm r$

If I'm not mistaken, Dirichlet's theorem states that if $(k,r)=1$ and $r<k$ then $\sharp\{p=kn+r,\mathbb{P}\ni p\leq x\}\sim \sharp\{q=kn-r,\mathbb{P}\ni q\leq x\}\sim\dfrac{1}{\varphi(k)}\pi(x)$. ...
2
votes
0answers
49 views

prove this inequality for sufficiently large n

Prove the following inequality for $n \geq 100$ $$\pi\bigg(\frac{\log (n^2+2n)}{\log 2}\bigg) < \pi(2n) - 1.5\pi(n)$$ $\pi(n)$ denotes to prime counting function
2
votes
1answer
37 views

I want an upper bound for a real function f(x,y,z) - prime counting

The function $f:\mathbb R^3\to\mathbb R$ is: $$\displaystyle f(x,y,z)=\frac{x}{yz}-\frac{\lfloor x/y\rfloor}{z} , \; \text{where}\,\; x,y,z>1.$$ If there is an upper bound less than 1, then it is ...
1
vote
2answers
58 views

Semiprime numbers of the form $246810121416$…

Concatenating the first even numbers $246810121416$...N, we might get a semiprime, but the only semiprime I know of such form is $2468101214$. I observe that numbers of the form $246810121416$... is ...
3
votes
1answer
81 views

Patterns in Sieve of Eratosthenes

Consider an integer sequence $$0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0...$$ Each term denotes the number of times the corresponding natural number, starting from $0$, was hit by ...
3
votes
0answers
61 views

Proof that the sequence of prime number is infinite. [duplicate]

Can someone please tell me how to prove that there is no last prime number? I am familiar with Euclid's one, but I'm looking for a different way. I'm in 11th grade and I can do intermediate algebra ...
6
votes
1answer
159 views

A conjecture about prime numbers based on $\sigma_1(n)$ and the Highly Abundant Numbers

I am trying to find the smallest expression $E(n)$, whose distances between the value of the expression and the next prime closer to the expression, $\mathcal{N}(E(n))$, and from the expression to the ...
0
votes
0answers
35 views

Congruence for an alternate sum of powers of the odd multiples of a prime

Let $p$ be an odd prime, and $m$ a positive integer, $$S(m,p)=\underset{0\leq k\leq p^{m+1}-1}{\underset{2 k+1\equiv 0 \bmod p}{\Sigma }}(-1)^k (2 k+1)^{m} $$ $S(m,p)$ is an alternate sum of the ...
1
vote
0answers
21 views

Count pairwise integer modulo

Assume $N$ and $M=(N-1)/2$ are both prime. For any $L(L\leq N)$ different integers $1\leq i_1<i_2<\ldots<i_L \leq N$, denote $A_m(i_1,\ldots,i_L)$, $1\leq m \leq M$ to be the number of ...
1
vote
1answer
38 views

Sum of hypercubes modulo $p$

Let $p$ be a prime number and $n$ a natural number. What is $\sum_{i=1}^{p-1} i^n$ modulo $p$ ? If $p>2$ and $n$ is odd it's easy to see that the sum is zero, but I don't see how to tackle this in ...
1
vote
1answer
60 views

math theory- primes problem

I have tried to prove it for over $15$ hours with no success. I got a clue to use the following technique: between $((P_n), \:2(P_n))$ there is an additional prime hiding there - $P_{n+1}$. ...
1
vote
0answers
38 views

Is there a standard mathematical way to analyze the gaps between elements of a reduced residue system modulo a primorial?

I've been very interested at the gaps the between the elements of a reduced residue system modulo a primorial $p\#$. The reason for this interest is that unlike the primes, the elements of reduced ...
1
vote
0answers
26 views

How to prove that there are infinite number of magic squares consisted of only consecutive prime numbers?

It is easy to find set of $N^2$ consecutive prime numbers (for small values of N) to build magic square (a square grid, where the numbers in each row, and in each column, and the numbers in the main ...
4
votes
1answer
39 views

What is the Diophantine Prime-Representing Polynomial with the Least Variables?

Recently I was reading Jones et al.'s famous paper "Diophantine Representation of the Set of Prime Numbers." They present a Prime-Representing Polynomial in 26 variables, and outline the construction ...
26
votes
0answers
347 views

Fractals using just modulo operation

Let us calculate the remainder after division of $27$ by $10$. $27 \equiv 7 \pmod{10}$ We have $7$. So let's calculate the remainder after divison of $27$ by $7$. $ 27 \equiv 6 \pmod{7}$ Ok, so ...
0
votes
0answers
24 views

Cousin primes in the Ulam Spiral

I was plotting the Ulam spiral (https://en.wikipedia.org/wiki/Ulam_spiral), and decided to isolate twin/cousin/sexy primes on the Ulam spiral. Although plotting twin primes offered no obvious lines, ...
4
votes
2answers
61 views

If $n$ is a product of primes, what is the number of divisors?

Let $n=p_1p_2...p_k$ Then the number of divisors is what? I assumed it was $1+ \binom k1+ \binom k2 + \binom k3 + ... + \binom kk=2^k$ Is this correct? Prove that the number of divisors is odd ...
4
votes
1answer
77 views

Summation of fractional parts $\frac{m}{n}$, where $2 \leq n < m$ (amateur)

I am looking for the result of the sum of the fractional part of the following number: $$f(m):=\sum_{n=2}^{m-1}Frac\left(\frac{m}{n}\right)$$ After some research I have found $2$ possible ...
1
vote
1answer
37 views

Sum of over the sets of reciprocal primes

I'm studying for my number theory exam tomorrow. On our study guide, there are a few questions that I have no idea about. Firstly, For a set S of prime numbers, explain why the sum $ ...
0
votes
1answer
50 views

What does auxiliary prime mean?

I'm writing a paper right now, in which Sophie Germain's theorem is included. Can anybody explain auxiliary prime θ to me? Context: Sophie Germain proved that the product $xyz$ must be divisible by ...
0
votes
0answers
56 views

Cyclic Group permutations

I am working on the following exercise question: Consider the following construction of a “keyed” hash function from Katz & Lindell (ex. 7.22 (1st ed.)/ 8.21(2nd ed.)). Gen : On input 1n , ...
-1
votes
2answers
69 views

$x^4 = -1$ (mod $p$) implies p = 1 mod 8

Let $p$ be an odd prime. Show that $x^4 = -1$ (mod $p$) has a solution if and only if $\Leftrightarrow p = 1$ (mod $8$)
3
votes
2answers
39 views

Prime ideals in $R= \left\{ \frac ab\in \mathbb Q\mid a,b\in \mathbb Z,p\nmid b \right\}$

Let $p\in \mathbb Z$ be a prime. Define $R= \left\{ \frac ab\in \mathbb Q\mid a,b\in \mathbb Z,p\nmid b \right\}$. I'm supposed to prove $pR$ is the only prime ideal in $R$, and the $R/pR\cong \mathbb ...
3
votes
2answers
52 views

does there exist a positive integer $X$ such that none of the integers $1+X,2+X,\ldots,x+X$ is the power of a prime number?

For which positive integers $x$ does there exist a positive integer $X$ such that none of the integers $1+X,2+X,\ldots,x+X$ is the power of a prime number? So this question is kinda confusing to ...
0
votes
0answers
34 views

Legendre symbol of $-n$

Let $x, y, n, p$ be positive integers such that $x^2 + ny^2 = p$, where $p$ is a prime such that $p \neq n$. Show that the Legendre symbol $(-n/p) = 1$.
8
votes
1answer
59 views

Prime Concatenation Order

Consider the following procedure. Given an integer $n \geq 2$, obtain the canonical prime factorization of $n$, i.e. $\prod_{i=1}^k p_i^{e_i}$. Take the distinct factors $p_i$ and list them in ...
0
votes
0answers
7 views

Inequalities Implying a Value of Jacobsthal's Function

Jacobsthal's function $g\colon\mathbb N\to\mathbb N$ is defined by letting $g(n)$ be the smallest positive integer $\ell$ such that any set of $\ell$ consecutive integers must include some element ...
4
votes
1answer
62 views

does there exist a prime such that…

Let $n>1$ be an non square positive integer (you can have it prime, if you wish), does there exist a prime $p>2$ such that $n$ generates the multiplicative group of $\mathbb F_p$? It sounds ...
0
votes
0answers
22 views

How to prove $G$ is cyclic? [duplicate]

Given that $G$ is a finite abelian group, and for every prime $p$ that divides the order of $G$, there is a unique subgroup of order $p$. How can I prove that $G$ is cyclic?
1
vote
1answer
23 views

Prove that $lcm(a , b) = \prod_{i=1} (P_i)^{\max(\alpha_i,\beta_i)}$

we are given that $a = p_1^{\alpha 1} .... p_k^{\alpha k}$ and $b = p_1^{\beta 1} .... p_k^{\beta k}$. Where $p_1 ... p_k$ are pairwise distinct primes and $\alpha_i$ and $\beta_i$ are non negative ...
7
votes
3answers
136 views

Computing the first $n$ values of the Liouville function in linear time

Is it possible to compute the first $n$ values of the Liouville function in linear time? Since we need to output $n$ values we clearly cannot do better than linear time, but the best I can figure out ...
2
votes
0answers
63 views

Pseudoprime $n$ to the base $b$ relation to $\prod\limits_{p\mid n}\gcd(p−1, n−1)$

Let $n > 1$ be an odd number, and let $P_n = \{b\pmod{n} : b^{n−1}\equiv 1\pmod{n}\}$ be the set of bases $b$ for which $n$ is a pseudoprime to the base $b$. Prove that $|P_n| = ...
1
vote
0answers
30 views

Show that there does not exist a simple group of order $120$. [duplicate]

Show that there does not exist a simple group of order $120$. By the Sylow's theorem, I already know that $N_5 | 24$ and $N_5 \equiv 1 \pmod 5$; I found that $N_5 \in \{1,6\}$ I think I can use ...
2
votes
2answers
48 views

Show that there does not exist a simple group of order $126$.

Show that there does not exist a simple group of order $126$. By the Sylow's theorem, I already know that $N_7 | 24$ and $N_7 \equiv 1 \pmod 7$; I found that $N_7 \in \{1,8\}$ I think I can use the ...
2
votes
1answer
84 views

$G$ is a finite abelian group. For every prime $p$ that divides $|G|$, there is a unique subgroup of order $p$.

$G$ is a finite abelian group. Assume that for every prime $p$ that divides $|G|$, there is a unique subgroup of order $p$. I'd like to prove that $G$ is cyclic. I'm thinking about the approach of ...
0
votes
3answers
31 views

Prove that if $n$ is a positive integer greater than one which is not prime then it is divisible by some prime $p \leq \sqrt{n}$

I have just started revising number theory and I am getting stuck on a lot of the "prove that" questions. Any tips and advice would be much appreciated!