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

Is there a systematic way of referring to a prime?

Is there a systematic scheme for identifying primes? For small numbers, it is easy to simply reproduce the whole prime, but for larger numbers, it seems like it could get cumbersome. For instance, ...
1
vote
2answers
37 views

How many $2$-Sylow subgroups in $G$ with $|G| = 2^2\cdot 3$?

I have a group $G$ with $|G| = 2^2\cdot 3$. I also know it has $4$ Sylow-$3$ subgroups. I need to show that there is $1$ Sylow-$2$ subgroup. (This is all I have left from the full question.) Any ...
6
votes
1answer
100 views

Prove for $2p +1$ divides $2^p + 1$

The following theorem is well known and already proven by Lagrange 1775 Let $p = 3$ (mod $4$) be prime. $2p+1$ is also prime if and only if $2p+1$ divides $2^p - 1$. But how can we prove this: Let ...
0
votes
1answer
30 views

For $n$ an even number and $p$ a prime, does $\lfloor {\frac {n}{4}} \rfloor= \frac{1}{\pi (n)-\pi (n/2)} \sum_{n/2<p<n} p-\frac {n}{2}$ hold?

I was playing around with prime numbers and I noticed that for $n$ an even number, the average of the distance between all primes between $n/2$ and $n$ and $n/2$ is equal to $\lfloor {\frac {n}{4}} ...
2
votes
1answer
56 views

Solutions of $(2x-1)^x\equiv1\mod\ p$ [closed]

Has the equation $(2x-1)^x\equiv 1\mod{p}$, for $p=1+6qx$, where $p$, $q$ are primes, $x$ is an odd integer and $x<p$ any solutions except $x=1$? Many thanks.
0
votes
1answer
66 views

Sum of primes at minimal $\gt t!$

$$2+3+5+17+97+599\cdots a_t \gt t!$$ What does that mean? Well it is a sum that follows specific rules. For one, the number of terms in the sequence is $t$. Similarly, $a_t$ represents the $t$'th ...
1
vote
1answer
31 views

Weierstrass factorization theorem and primality function

I'm interested in application of the Weierstrass factorization theorem to the primality function. Let $np(x)\colon \mathbb N\to \mathbb N$ is a "not-prime" function: $$ np(x) = \begin{cases}1, & ...
1
vote
1answer
24 views

A congruence for the prime counting function in Wolfram.What does it actually say?

I saw today in functions.wolfram.com a congruence for the prime counting function which says $\binom {2prime(k)-1} {prime(k)-1} \pmod{prime(k)^3}=1$ (the third congruence at the bottom). What does ...
0
votes
2answers
47 views

On primality of the numbers of the form $10^{2k} - 10^{(k+1)} -1$

Has anyone seen proof that numbers of the form $10^{2k} - 10^{k+1} - 1 \space \forall k \ge 2$ are prime?
2
votes
2answers
32 views

Using a sieve and Mertens' theorem to show a formula for $\pi(x)$ - Does this work?

When I was younger, just starting highschool, I loved tinkering with prime sieves. I still have notes that I took. I had written down that $$\pi(x)\sim x\prod_{n=1}^m\frac{p_n-1}{p_n}+m-1.$$ ...
3
votes
3answers
68 views

Number of primes from $n!+1$ to $n!+n$

Why aren't there any primes between $n!+1$ and $n!+n$ for all $n>1$? This question was on AHSME 1969 #23, but the question is trivial because it's multiple choice. However, I have no idea how to ...
2
votes
1answer
61 views

Intersection between the sums of the first integers, primes and non primes

Conjecture : $$\left\{\sum\limits_{\begin{array}{c}k=1\\k\in\mathbb{Z}\end{array}}^nk \ |\ n\in\Bbb Z\right\} \cap \left\lbrace ...
4
votes
2answers
69 views

If for almost all $p \equiv 1$ (mod a) it holds that $p \equiv 1$ (mod m), then…

Let $a,m\in \mathbb N$ Suppose that for almost all primes $p \equiv 1$ (mod a) we have that $p \equiv 1$ (mod m) Can we say something about $a$ and $m$? For example $m$ divides $a$ or vice versa? I ...
3
votes
2answers
34 views

Is it known whether there are ever infinitely many primes of the form $\prod_i p_i^{n_i} + 1$ where the $p_i$ are fixed primes but the $n_i$ can vary?

So if we fix finitely many primes $p_i$, where one $p_i$ is $2$, but let the powers $n_i$ on the $p_i$ vary, is it known whether it is ever possible to have infinitely many primes of the form $\prod_i ...
3
votes
1answer
48 views

Comparing $\pi(x)$ and $\pi^{(k)}(x)$

We say a k-almost prime is an integer that results as the product of k prime, counting repetition. For example, $12$ is a $3$-almost prime as $12= 3 \times 2 \times 2$. Additionally, we define ...
0
votes
0answers
9 views

Convenient goedel numbering for finite register machines?

Overview I'm trying to find a goedel numbering for finite register machines, which is convenient in two ways: when ordering machines by their numbering, simple machines shall come first, i.e. ...
2
votes
1answer
70 views

How do computers generate primes so quickly?

From what I understand, when a computer encrypts a file using an encryption standard like RSA, one of the steps is to generate two large primes, and multiply them together. I have created RSA keys on ...
-2
votes
0answers
33 views

Primes with a very special form [duplicate]

This question is related to the power cyclic and congruences. Does there exist a prime of the form 2^3^5^7^11^13^....^p(n-1)^p(n)+ p(n)^p(n-1)^p(n-2)^....^11^7^5^3^2 where p(n) is the n-th prime ...
6
votes
2answers
301 views

Smallest Positive Integer Not Coprime to a Collection of Consecutive Integers

Let $n\in\mathbb{N}$. Define $f(n)$ to be the smallest positive integer $m$ such that there exists a positive integer $k$ for which $k+i$ is not relatively prime to $m$ for every ...
6
votes
0answers
133 views

Is there a quicker way to generate integers which are hard to factor than multiplying two large primes?

An easy way to generate an integer which is hard to factor is to find two large primes and multiply them. As a bonus, you know the factors. I'm interested in whether it's possible to find integers ...
1
vote
2answers
20 views

Distribution of decimal repunit primes

The prime number theorem describes the distribution of prime numbers in positive integers. Is there a similar theorem describing the distribution of primes among positive integers of the form ...
0
votes
1answer
40 views

Time complexity of a simple factoring algorithm?

This has puzzled me for a little. I start off with a list of primes that is sufficiently large. For my number $n$, I do trial division of primes in ascending order until I reach a prime that divides ...
0
votes
1answer
73 views

Using The Riemann Zeta Functional Equation

Riemann was able to establish the following link between the Riemann zeta function and the weighted prime counting function $J(x)$. $$\ln(\zeta(s))=s\int_1^\infty J(x)x^{-s-1}dx$$ Using the Mellin ...
1
vote
0answers
43 views

Probability number is divisible by half the square of a prime?

Let $p$ be a prime. What is the probability that a number of the form $\left \lceil \frac{p^2}{2} \right \rceil$ divides a random positive integer $n$. I have a solution that involves the Riemann-Zeta ...
3
votes
1answer
27 views

Is there a way to estimate the number of positive integers less than or equal to $n$ that have a given prime $p$ as a least prime factor

The probability that an integer $p$ divides an integer $x$ is $\dfrac{1}{p}$. From this article on almost prime numbers, the number $\pi_k(n)$ of positive integers less than or equal to $n$ with at ...
7
votes
1answer
99 views

Distribution of the sum reciprocal of primes $\le 1$

$$\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}+\cdots \le 1 $$ This is an interesting infinite summation. This is very closely resembling my other problem with has to do with the distribution of ...
5
votes
1answer
87 views

Finding Gaussian Primes along Lines in $\mathbb Z[i]$

I am trying to prove the following statement: For all positive integers $a$ does there exists a positive integer $b$ such that $a^2 + b^2$ is prime? (If so, can we provide such a $b$?) Given the ...
0
votes
1answer
22 views

Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n

Given the number $n=35$.Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n I found this problem on internet and i am trying to find a solution ...
2
votes
3answers
48 views

Find all numbers that have 30 factors and have 30 as one of their factors.

Find all numbers that have 30 factors and have 30 as one of their factors. Thank you. Note: please show way if possible.
1
vote
2answers
73 views

Do prime numbers have prime factors?

(This is a somewhat trivial question). Do prime numbers have prime factors, i.e. itself? For example is 7 a prime factor of 7? The reason I ask this is because there is a statement in my lecture ...
1
vote
1answer
30 views

Find the smallest prime number that doesn't divide any 5-digit number whose digits are in strictly increasing order.

Find the smallest prime number that doesn't divide any 5-digit number whose digits are in strictly increasing order. I have posted an answer of my own below; any alternative solutions will also be ...
1
vote
0answers
34 views

Why does symmetry happen in reset-based random walks?

I am studying the basic concepts about random walks / brownian motion, and based on the idea of a Möbius-based walk in Wolfram's website, I wanted to try my own version of it in Python to compare it ...
0
votes
1answer
20 views

What is the summatory function of the number of (not necessarily distinct) prime factors?

In the Math World article on Merten's Constant, a related constant $B_2$ is mentioned which "appears in the summatory function of the number of (not necessarily distinct) prime factors." I am very ...
3
votes
2answers
50 views

How is the Twin Primes Constant useful? What value does it provide over Brun's Constant?

The Twin Primes Constant is: $$\prod_{p > 2 \text{ and a prime }}\left(1 - \frac{1}{(p-1)^2}\right) = 0.6601618158\ldots$$ It appears that in this case $p$ does not have to be a prime. But if ...
1
vote
4answers
87 views

How do I show that:if$p$ is prime $>5$ then $p^4-20p^2+19$ is always divisible by $180$.?

Is there someone who can show me How do i show that :If $p$ is a prime number greater than $5$ then : $$p^4-20p^2+19$$ is always divisible by $180$. Note : i think should factor $p^4-20p^2+19=$ ...
2
votes
0answers
29 views

Prime from mirror concatenation of first primes

The mirror concatenation of the first 1, 6 and 8 prime numbers with no primes being reversed is a prime ! i.e. 131175323571113 and 19171311753235711131719 are prime numbers! (beautiful primes!). After ...
1
vote
1answer
231 views

How to get this equation solved?

I came across this equation $$\sqrt a-\sqrt b=\sqrt 7-\sqrt 5$$ And you have to find the value of '$a$' and '$b$' when both of them are primes. The solution was $a=7, b=5$. Now, my question is, ...
2
votes
1answer
68 views

Proof that $2^n-1$ does not always generate primes when primes are plugged in for $n$?

Exactly what the name entails. The function $2^n-1$ I see largely tends to generate primes when $n$ is prime. However, a week ago I heard that this was horribly false. Please show me a disproof.
10
votes
4answers
404 views

Is there a function that can be subtracted from the sum of reciprocals of primes to make the series convergent

The gamma constant is defined by an equation where the harmonic series is subtracted by the natural logarithm: $$\gamma = \lim_{n \rightarrow \infty }\left(\sum_{k=1}^n \frac{1}{k} - \ln(n)\right)$$ ...
2
votes
3answers
44 views

Proving that $i! \mid (p-1)\cdot(p-2)\cdots(p-i+1)$ for $i < p$

Started solving this problem: $$ (a+b)^p \equiv a^p+b^p \pmod{p}$$ where $p\in\mathbb{P}$, $a,b\in\mathbb{Z} $ After a few implications I arrived to this $$ i! \mid ...
5
votes
5answers
96 views

what is the greatest integer that divides $p^4-1$ for every prime number p greater than 5

what is the greatest integer that divides $p^4-1$ for every prime number p greater than 5(this is a gre subject math problem) I think that $p^4-1=(p^2+1)(p-1)(p+1)$,so 8 must divide all the $p^4-1$ ...
3
votes
1answer
48 views

Inverse of prime counting function

The prime counting function $ \pi (x) \approx \dfrac {x} {\ln(x-1)} $. This function returns the number of primes less than $x$. Note: $x-1$ gives a better estimate than $x$. How to find $x$ given $ ...
1
vote
1answer
48 views

If Wieferich primes are finite…Then what?

I am wondering if $1093$ and $3511$ are the only Wieferich Primes, then what would it imply? (A wieferich prime is a prime satisfying the congruence $2^{p-1}\equiv 1\ mod \ p^2 $). I know of 3 cases; ...
0
votes
1answer
71 views

Are all even numbers the difference of prime powers

Does there exist an even positive integer greater than $100$ (to eliminate trivial cases) that cannot be expressed in the form: $p^2-q$ $p-q^2$ $p^2-q^2$ $p^3-q^3$ where $p$ and $q$ are primes.
1
vote
1answer
66 views

Quadratic polynomials describe the diagonal lines in the Ulam-Spiral

I'm trying to understand why is it possible to describe every diagonal line in the Ulam-Spiral with an quadratic polynomial $$2n\cdot(2n+b)+a = 4n^2 + 2nb +a$$ for $a, b \in \mathbb{N}$ and $n \in ...
6
votes
1answer
72 views

Is $\pi(n)$ a Rational Function?

Are there some two-variable polynomials $P(n,\log n)$ and $Q(n,\log n)$ which we have the bellow equation for prime counting function $\pi(n)$ for $n \in \mathbb{n}$? $$\pi(n) = \Bigl{\lfloor} ...
4
votes
1answer
47 views

Prime Zeta Function proof help: Why are these expressions not equal?

I was trying to create a formula for the Prime Zeta function and I partially succeeded except for one frustrating error. I was only able to formulate an approximation. Consider the following sum: ...
2
votes
2answers
71 views

$\pi(x)$ Proof Clarification

In a proof from a number theory book that $${\pi(x) \over x}\le {2k \over x} + {\phi(k) \over k}$$ Where $x=kl+r$ with $0 \le r\lt k $ It is stated that $$\pi(x) \le k+(l-1)\phi(k) + r \le 2k+{x\over ...
3
votes
1answer
43 views

Usefulness of prime numbers as Threading Timeouts in programming [closed]

I am a .NET programmer, founded in math. I am having an argument with a fellow programmer. When I add a Threaded Timer to the program, the interval in milliseconds I use is always a prime number. ...
0
votes
1answer
86 views

Is $u_n$ where $\left\{\begin{matrix}u_{1}=5 \\ u_{n}=\frac{2^{u_{n-1}}+1}{3} \end{matrix}\right.$ always prime?

$\left\{\begin{matrix}u_{1}=5 \\ u_{n}=\frac{2^{u_{n-1}}+1}{3} \end{matrix}\right.$ I conjecture that $u_{n}$ is prime number. But I can not prove it. So I want to know my conjecture is right or ...