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.

learn more… | top users | synonyms

2
votes
1answer
73 views

Finding 8 co-primes $\le 2^n$

We can find 8 co-prime integers $\le 2^n$ for sufficiently large $n$. I'm looking for asymptotic bounds for the minimum distance away from $2^n$ we have to go before finding 8 co-primes. In other ...
3
votes
1answer
914 views

Explain Carmichael's Function To A Novice

I understand that the Carmichael Function (I'm going to call C()) is essentially the smallest positive integer m, where $a^m$ is congruent $1 \pmod n$ for all $a$ co-prime to $n$ and less than $n$. 6 ...
1
vote
1answer
103 views

Why are the first 5 Fermat numbers prime?

The $n$th Fermat number $F_n$ is defined as $F_n = 2^{2^n}+1$. The first five Fermat numbers, $F_0,F_1,F_2,F_3,F_4$, are all prime. Why is this? It seems like a fairly surprising coincidence that ...
1
vote
2answers
67 views

prove if n - natural number divide number $34x^2-42xy+13y^2$ then n is sum of two square number

prove if n - natural number divide number $34x^2-42xy+13y^2$ where x,y are relatively prime then n is sum of two square number. I don't know what is going on in this exercise. I will be grateful ...
8
votes
4answers
250 views

Is the sum of the first $n$ primes a prime infinitely many times?

Define the sequence $P(n)=\sum_{i=1}^{n}p_i$, where $p_i$ is the $i$-th prime number. I observed for some small $n$ that sometimes this sum evaluates to a prime number, for example $P(2)=2+3=5$ and $...
1
vote
2answers
68 views

Find out if a number is prime [duplicate]

I read that every prime number is of the form $6k\pm1$, is this a correct approach to find out if a number is prime? ...
1
vote
2answers
70 views

checking if a number is a prime

I was reading Wikipedia, and it was given that "all primes are of the form 6k ± 1" (other than 2 and 3), where k = 1,2,3,4,... Is this statement correct? If yes, can we use this to test if a given ...
5
votes
1answer
282 views

Elementary proof there are infinitely many primes of the form $4n+1$

My attempt: $4n+1$ is odd. Thus its decomposition must not contain $2$. Every odd number is either of the form $4k-1$ or $4m+1$. $(4m+1)(4k-1)$ is never of the form $4n+1$. So $4n+1$ has factors ...
2
votes
2answers
107 views

Numbers $m = pq^4$ ($p,q$ are distinct primes) for which $m$ divided by the number of its factors is an integer

The $\operatorname{Ionof}$ (Integer on number of factors) of an integer is the integer divided by the number of factors it has. For example, $18$ has $6$ factors so $\operatorname{Ionof}(18) = \frac{...
2
votes
1answer
34 views

Prove that $3^{(q-1)/2} \equiv -1 \pmod q$ then q is prime number.

$q=2^m+1, m\ge 2$. Prove that if $$3^{(q-1)/2} \equiv -1 \pmod q$$ then q is prime number. I want to use if $q-1 | \phi(q)$, then q is prime number. But I don't know how to transform above equation. ...
2
votes
0answers
61 views

What is this function, and what are it's properties?

I made a function that determines how "prime-y" a number is; if $f(x) = 1$ then $x \in primes $. The function is $$f(x) = \frac{\pi(x) - \#\{p \in primes | p<x, p \space| \space x\}}{\pi(x)}$$ ...
7
votes
1answer
80 views

Is there always a prime between a prime and prime plus the index of that prime?

Is it known is there always a prime strictly between $p_n$ and $p_n+n$, where $p_n$ is the $n$-th prime number and $n\geq5$? I know about Bertrand`s postulate which states that for any integer $n>...
2
votes
1answer
47 views

Is always two times an even semiprime at a distance $1$ or prime to the closest previous odd semiprime?

This is an observation regarding the semiprimes, also named 2-almost primes, biprimes, or the product of two primes. This week I do not have a computer, only a tablet (hospitalized with a lot of free ...
3
votes
1answer
217 views

Conjecture about Rabin-Miller pseudo prime test

I tested the Rabin-Miller pseudo prime algorithm using a single test value and found that the number of false calls depends on the size of the number to test, reducing to a (conjectured) negligible ...
2
votes
0answers
26 views

Convergence of the sum $\sum\limits_{p}^{}\sum\limits_{k=1}^{\infty}\frac{\log p}{p^{ks}}$

How can I prove the following sum converges, where $s>1$ and the sum is over all primes. $$\displaystyle\sum_{p}^{}\displaystyle\sum_{k=1}^{\infty}\frac{\log p}{p^{ks}}$$ I've tried grouping terms ...
7
votes
5answers
964 views

Connections between prime numbers and geometry

This might be a little open-ended, but I was wondering: are there any natural connections between geometry and the prime numbers? Put differently, are there any specific topics in either field which ...
2
votes
1answer
40 views

find all primes $p$ and $q$ such that $p \cdot q | 2^p + 2^q$

I have to find all prime numbers $p,q$ such that $p\cdot q | 2^p + 2^q$. I don't know from what I have to start.
4
votes
0answers
66 views

Sorting prime numbers on two sets of equals weights

Lets denote $(p_n)$ the sequence of all prime numbers $(p_1=2, p_2=3,\ldots)$. The conjecture is the following. For infinitely many $n\in \mathbb N_{\geq 1}$ $$\exists I \subset \{1,\ldots n\...
1
vote
1answer
36 views

Modified Sum of Products

A given number k is to be expressed as a sum of products of integers keeping in mind that the integers used in above process do not exceed their cumulative sum as 100. For e.g., k = 19 can be ...
1
vote
0answers
34 views

Prove by contradiction that : There are Infinite Primes. [closed]

Specify $P$, ~$P$,Q and ~$Q$; For this proof I am having difficulty understanding what p and q signify. I was reading Euclid proof http://www.math.utah.edu/~pa/math/q2.html . But I do not quite ...
1
vote
1answer
54 views

proof of the prime number formula(It's real)

Proof that this formula always generates primes.Also it generates all primes(grate prime numbers formula) I have tried this formula it also generates primes orderd except the prime 2. I am really ...
1
vote
1answer
64 views

Prove that if $ p | x^p + y^p $ where $p$ is a prime number greater than $2$, then $p^2 | x^p + y^p$

I was trying to solve the following problem recently: Prove that if $ p | x^p + y^p $ where $p$ is a prime number greater than $2$, then $p^2 | x^p + y^p$. Here $x$ and $y$ are both integers. $a|b$ ...
1
vote
2answers
44 views

positive three-digit prime numbers

I can solve this problem by typing "prime number under 200" in google and then examining three-digit prime numbers. My question is whether there is way to solve the problem without remembering all the ...
1
vote
1answer
62 views

Does this set contain an infinite number of prime numbers?

I know that it still is not known whether the sequence $n^2+1$ contain an infinite number of prime numbers. I guess that this is also not known for any sequence of the form $n^k+1$ where $k\geq2$ is ...
2
votes
2answers
2k views

How to solve difficult positive integers and co-prime word problem?

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with derivative of algebra and prime numbers, which yields the shortest, ...
2
votes
1answer
31 views

Numbers obtainable in two ways as a sum over complementary subsets of a set of primes

Let $\{p_1,p_2,\ldots ,p_r\}$ be a set of distinct primes. Denote the set $\{1,2,\ldots ,r\}$ by $C$. Now, let $A,B\subset C$ such that $$A\cup B=C, \quad A\cap B=\emptyset.$$ These sets are called $\...
7
votes
1answer
113 views

What is the smallest composite number

I got the correct answer for the following problem by trying all numbers. It's very time consuming. Can anyone tell me whether there is a simple and easy way to solve the problem? What is the ...
1
vote
0answers
20 views

How many ordered triples of primes $(a, b, c)$ exist

Is there any easy way to find the answer to the following problem without trying numbers one by one? How many ordered triples of primes $(a, b, c)$ exist such that $a+b+c=37$?
12
votes
1answer
98 views

Permutations of the set $\{1,2,…,n\}$ and prime numbers

I just observed for some small $n$ that we can find a permutation of the set $\{1,2,...,n\}$ which is such that sum of any two adjacent numbers is a prime number. Take for example set $\{1,2,3,4,5,6\}...
0
votes
1answer
112 views

A new PI prime number? [closed]

A Pi prime is a prime number formed from the first n digits of the decimal expansions of constant PI=$3.14159265358979$...The largest such prime we know is $78073$ digits, which is the first $78073$ ...
1
vote
5answers
151 views

Solve $ord_x(2) = 20$

Given that the (multiplicative) order of $2$ mod $x$ is $20$, how can I work out what $x$ is?
1
vote
1answer
40 views

Positive integral solutions of $\pi(x)+\pi(y)=2\pi\left(\dfrac{x+y}{2}\right)$

Recently I was reading one of my earlier posts. There it has been conjectured that, For all sufficiently large $x,y$ we have, $$\pi(x)+\pi(y)\le 2\pi\left(\dfrac{x+y}{2}\right)$$ But it turned ...
3
votes
1answer
33 views

Primes with $p^9\pm1 = q^4r$

Are there distinct primes $p,q,r$ with $$ p^9\pm1 = q^4r $$ ? This is related to a series of conjectures going back to Erdos regarding $d(n)=d(n+1)$. Of course either $q$ or $r$ is 2.
0
votes
0answers
35 views

If $n$ is divisible by a perfect square then $n$ is not a Carmichael number.

If $n$ is divisible by a perfect square then $n$ is not a Carmichael number. Going through the proof from Neal Koblitz's A Course in Number Theory and Cryptography...I am facing some difficulties to ...
-5
votes
2answers
72 views

Is the largest prime number known? If yes then show. If no then prove. [closed]

I am not sure whether is known or not, I supposed not but don'nt know how to prove.
9
votes
1answer
114 views

Calcule $\gcd(0!+1!+\ldots+n!, (n+1)!)$

I have to compute $d=\gcd(0!+1!+\ldots+n!, (n+1)!)$, so let $a=0!+1!+\ldots+n!$ and $b=(n+1)!$. Then: $a=0!+1!+\ldots+n!=3!+0!+1!+2!+4!+...+n!=6+4+4!+...+n! \equiv 2 \mod 4$ Thus, $a$ and $b$ are ...
0
votes
1answer
56 views

Divisibility of a summation by $p^2$

I try to use the hint of this problem but I could not. Any detailed answer will be appreciated! Let $p$ be a prime number which $p>3$, and $$a/b:=1+1/2+1/3+\cdots +1/(p-1).$$ How could we show ...
3
votes
2answers
33 views

A congruence mod p

Let $p$ be a prime number. Show that $$2^2\times 4^2\times \cdots \times (p-1)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod {p} .$$ Any help will be appreciated!
0
votes
0answers
55 views

Primality test for Thabit numbers of the first kind

Definition 1 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)$ , where $m$ and $x$ are nonnegative integers . Definition 2 Let $T_n=3 \cdot 2^n-...
12
votes
0answers
181 views

Have I discovered an analytic function allowing quick factorization?

So I have this apparently smooth, parametrized function: The function has a single parameter $ m $ and approaches infinity at every $x$ that divides $m$. It is then defined for real $x$ apart ...
1
vote
1answer
31 views

Can a polynomial $p(x)$ generate only primes and 2-almost primes $\forall x \ge 0 \in \Bbb N$ or there is also a restriction for this to happen?

There is a simple demonstration to show that a polynomial of any degree can not generate only primes. Basically, if $p(x)=a_nx^n+...+a_1x^1+a_0$ is prime for every $x \in \Bbb N$ ($\Bbb Z$ would be ...
4
votes
1answer
67 views

Asymptotic density of Zhang's primes

By this point, it is well known that Yitang Zhang's result implies for some $c$, there are infinitely many primes $p$ such that $p+c$ is also prime, and that the smallest such $c$ is less than $70,000,...
3
votes
3answers
415 views

Do Gödel numbers have a practical use?

Is there any example of Gödel numbers being actually used in practice? If so for what purpose?
-2
votes
2answers
63 views

Is there any formula to find prime numbers

I have found from a site this formula: Ok.I have found that this formula is correct.see the reason below. This part of formula is always $1$ or $zero$. it's zero when $(2m)!+1$ isn't dividable ...
3
votes
3answers
208 views

The ultimate formula to factor them all.

Context I am working on Integer factorization problem, I found a formula for factoring numbers, and I need your help to simplify it. First I will explain how I get there and then I present the ...
5
votes
3answers
297 views

Show that the square of any prime number is the Factof of some integer

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with prime numbers, but other than that, the textbook gave no hints really and ...
2
votes
1answer
232 views

Show that the square of any prime number is the IONOF of an integer. [duplicate]

This has been asked here: IONOFs Problem Solving Solving a Word Problem relating to factorisation But they did not provide context or examples The ionof of an integer is the integer divided by ...
1
vote
2answers
71 views

For any consecutive natural numbers $a_1,a_2$ are there infinitely many primes $p,q$ such that: $a_1<\dfrac{p}{q}<a_2$?

Progress: Let $a_1,a_2$ consecutive natural numbers; prove or disprove the infinitude of distinct prime pair $p,q$ which satidfies: $a_1<\dfrac{p}{q}<a_2$ The most challenging part of the ...
4
votes
1answer
54 views

Prove that if $p \mid a-b$ then $p^{n+1} \mid a^{p^n}-b^{p^n}$

I need help with the following problem, I don't know how to continue. Let $p$ be a prime. Prove that if $p \mid a-b$ then: $$p^{n+1} \mid a^{p^n}-b^{p^n}$$ At first I thougt the following: $$p \mid ...
2
votes
2answers
45 views

Estimate for a prime product.

Is there a bound for $$\prod_{i=1}^{m}\Big(1-\frac{1}{p_i}\Big)$$ where $p_i$ is $i$th prime? What if $m=O(\log n)$?