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
2answers
36 views

Quadratic equation solutions modulo prime p

the question is: find all primes p that satisfy the equation: x^2-2*x-5 = 0 (mod p) The discriminante is 24, and I know that the equation mod p has a solution ...
4
votes
1answer
63 views

The limit of consecutive positive integers which are the product of n primes.

The maximum length of a string of consecutive primes is 2: that is, the primes 2, 3. This is easily proven, as no even number other than 2 is prime. In contrast, consider the set of numbers which ...
12
votes
2answers
1k views

Why can no prime number appear as the length of a hypotenuse in more than one Pythagorean triangle?

Why is it that no prime number can appear as the length of a hypotenuse in more than one Pythagorean triangle? In other words, could any of you give me a algebraic proof for the following? Given ...
1
vote
1answer
130 views

Discrete log for prime powers

I was fiddling around and found that a function of the form $$L_b (x)=\left(\frac{b^{\phi (p^k)}-1}{p^k}\right)^{-1}\left(\frac{x^{\phi (p^k)}-1}{p^k}\right) \mod p^k$$ seems to behave similarly to a ...
4
votes
0answers
55 views

Why using primes as base in the Rabin-Miller test?

I have done some computer tests with the Rabin-Miller primality test: To test an odd number $n$, write $n=2^r\cdot s + 1$, where $s$ is odd. Given a number $a$ such that $1<a<n-1$, if $...
1
vote
1answer
46 views

on the uniqueness of special-prime gaps

I was studying a particular type of prime numbers, and I noticed an interesting property which I wish to prove or disprove. Consider the set $S = \{10p + 1, 10p + 3, 10p + 7, 10p + 9\}$ (where p is a ...
3
votes
1answer
191 views

Show that $101!+1$ is not prime number [closed]

Show that $101!+1$ is not prime number. How many ways exist to do it?
1
vote
1answer
55 views

What is an open set in this prime number related topology?

Define a topology on $X=\mathbb N$: $A\subset X$ (proper subset) is closed if and only if: $\:A$ is finite; $\:n\in A\wedge p\in\mathbb P\wedge p|n \implies p\in A$. A nonempty open subset is ...
0
votes
2answers
63 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
61 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) ...
2
votes
0answers
37 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 ...
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 ...
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? ...
6
votes
1answer
98 views

A question on the prime generating polynomial $x^2 -79x+1601$.

In Tom Apostol's book Analytic Number Theory, author says $x^2 -79x+1601$ gives prime numbers for $x=0,1,...,79$. We can see this by putting values. Is there any other way of knowing this property of ...
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)}$$ ...
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. ...
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
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 ...
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\...
0
votes
0answers
28 views

Legendre's Conjecture Theme (Part II)

This is a continuation of this question. My main question is that, in the previous question we were mainly concerned about the sign of, $$f_{2}(n)=\pi\left((n+1)^2\right)+\pi\left(n^2\right)-2\pi\left(...
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 ...
2
votes
0answers
72 views

Legendre's Conjecture Theme (Part I)

Main Question Recently I have been thinking about the Legendre's Conjecture. I noticed that a proof of the conjecture can be obtained if we can prove any one of the following, Conjecture 1. For ...
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
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 ...
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 $...
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 $\...
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
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$?
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 ...
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.
1
vote
2answers
65 views

If $b^2 \equiv 1 \pmod 3$, is it possible to have $\sigma(b^2) \equiv b^2 \pmod 3$?

The title says it all. Let $\sigma(N)$ denote the sum of the divisors of the positive integer $N$. To paraphrase my question: If $3 \mid \left(b^2 - 1\right)$, is it possible to have $3 \mid \...
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 ...
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!
10
votes
0answers
170 views

Are my calculations of a new constant similar to Mill's constant based on $\lfloor A^{2^{n}}\rfloor$ and Bertrand's postulate correct?

As Wikipedia explains in number theory, Mills' constant is defined as: "The smallest positive real number $A$ such that the floor function of the double exponential function $\lfloor A^{3^{n}}\...
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 ...
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 ...
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,...
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 ...