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

0
votes
2answers
58 views

Prime number and Stone game. Who will win?

2 players 'A' and 'B' are playing a game. A piles of Stone has n stones.Player can remove either one stone or stone equal to power of some prime number. The player who can not make a move in his turn ...
1
vote
0answers
59 views

The next Michael's neat primes

Concatenate the first k prime numbers and then rearrange all the original digit's positions into successive digits from smallest to largest: k=1: 2 (prime) k=2: $23$ (prime) k=3: $235$ (composite) ...
4
votes
1answer
379 views

Find the Least Prime Divisor of $2^{17}-1$

Show that the least prime divisor of $2^{17}-1$ is $2^{17}-1$ itself. This question is really anoying. Let $N=2^{17}-1$. What I know is that if $q\mid N$, then $q=34k+1$ for some $k \in \Bbb{N}$ and ...
2
votes
0answers
35 views

Pattern involving squares, primes, and remainders

I ran across a really neat pattern, wholly by accident. In advance, my questions are: Has this been discovered before? If so, where can I learn more about it? Why does this pattern work? Now for ...
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
895 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
101 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
233 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
67 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
106 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
79 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
25 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
925 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
38 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
65 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
35 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
29 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
2answers
61 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
41 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
30 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
88 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
18 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
91 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
105 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?
7
votes
2answers
282 views

A conjecture about the prime function $p_n$

While testing my system Zet for computational mathematics I find possible relations now and then. The latest is: Conjecture: For all $(m,n)\in\mathbb Z_+^2$ except $(3,4),(4,3) \text{ and } (4,4)$...
1
vote
1answer
39 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
32 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
71 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
111 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
31 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
52 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
174 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
61 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
402 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
62 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 ...