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

Does there exist prime number of the form $0^0+1^1+2^2+3^3+4^4+…$ after the trivial one $2$?

I am interested with prime numbers of the form $0^0+1^1+2^2+3^3+4^4+....(n-1)^{n-1}+ n^n$ (where we take $0^0=1$). I've checked $n$ up to $250$, and I found that numbers of such form are very very ...
2
votes
1answer
129 views

The following is a necessary condition for a number to be prime, from its digit expansion. Has it been referred somewhere?

Concerning a numbers’ digits we know some necessary conditions on them for the number to be prime, besides the last digit having to be odd (except for prime 2). For example in decimal representation ...
1
vote
1answer
21 views

Proving the complete additivity of the Big Omega function $\Omega(n)$ (total number of prime factors of n) .

The Big Omega function $\Omega(n)$ gives you the total number of prime factors of the number n. A function $f(x)$ is completely additive if $f(ab)=f(a)+f(b)$ for all positive numbers $a$ and $b$, ...
4
votes
1answer
61 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 ...
0
votes
3answers
248 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.
2
votes
0answers
44 views

Usefulness of largest known prime [duplicate]

Does it make sense to keep track of largest known prime? In other words: Are there any (more or less practical) situations, where we need the largest known prime? (except of the "situation" of ...
3
votes
1answer
58 views

Is $S_i(1,2,\dots,p-2) \equiv 1 \pmod{p}$ for all values of $i$ whenever $p$ is prime?

Let $S_i(x_1,x_2,\dots,x_n)$ denote the $i$th elementary symmetric polynomial in $n$ variables. Is $S_i(1,2,\dots,p-2) \equiv 1 \pmod{p}$ for all values of $i$ from $0$ to $(p-2)$ whenever $p$ is ...
-1
votes
0answers
28 views

Function which gives number of primes STRICTLY less than a number x.

We all know that the $\pi(x)$ function (Prime-counting function) gives us the number of primes less than or equal to x. I'm interested in the function which specifically gives the number of primes ...
4
votes
0answers
50 views

Do DSm(n) never be a prime?

Smarandache number (denoted as Sm(n)), is a number formed from concatenating the first n natural numbers. For example Sm(11)= $1234567891011$ (http://mathworld.wolfram.com/SmarandacheNumber.html). And ...
1
vote
0answers
72 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 ...
0
votes
0answers
26 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(...
2
votes
0answers
64 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
2answers
52 views

Prove that $6ab-1$ primes infinite?

Is there any demonstration that there are an infinite amount of primes of the form $6ab-1$ being $a$ and $b$ integers?
0
votes
5answers
246 views

Euclid's proof of infinitude of primes.

http://en.wikipedia.org/wiki/Euclid's_theorem I just read Euclid's proof for the existence of infinitely many primes (I have never used his proof earlier to prove this). It seems to me that he ...
4
votes
5answers
514 views

If a prime $p$ is divided by 30, remainder is either prime or 1

Show that if a prime number $p$ is divided by 30, then the remainder is either a prime or 1. I did the sum sum but cannot complete it. I took $p=6k+1$ and $p=6k-1$ form. now for any $k=5m$ we get $6k=...
2
votes
2answers
34 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 ...
6
votes
1answer
92 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
1answer
123 views

How can can you write a prime number as a product of prime numbers?

According to the fundamental theorem of arithmetic (unique factorization theorem), you can write every number as the product of some prime numbers, for example $33 = 11 \cdot 3$. However, how can you ...
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 ...
6
votes
0answers
222 views

Does the set of $m \in Max(ord_n(k))$ for every $n$ without primitive roots contain a pair of primes $p_1+p_2=n$?

I have made the following observation: for those n even numbers that do not have primitive roots modulo n ,$Pr(n)$, the set $M(n)$ of those $k$ having a maximum multiplicative order $ord_n(k)$ ...
11
votes
3answers
1k views

A theorem about prime divisors of generalized Fermat numbers?

A theorem of Édouard Lucas related to the Fermat numbers states that : Any prime divisor $p$ of $F_n=2^{2^n}+1$ is of the form $p=k\cdot 2^{n+2}+1$ whenever $n$ is greater than one. Does anyone ...
3
votes
0answers
52 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 $...
5
votes
1answer
615 views

How to prove that if a prime divides a Fermat Number then $p=k\cdot 2^{n+2}+1$?

If a prime $p$ divides a Fermat Number then $p=k\cdot 2^{n+2}+1$? Does anyone know a simple/elementary proof?
3
votes
2answers
137 views

Prime larger than a twin prime

Wondered whether the following equation holds true for all twin primes such that where $a$ and $b$ are twin primes and where $b=a+2$, then $3\left[\left(\frac{a+b}{2}\right)^2-1\right]+2 = NP$. Where ...
3
votes
0answers
47 views

Maier's theorem

I have some questions with Maier's theorem If $1 < \lambda < 2$, then what? If $x+(\log x)^\lambda = x^{1+1/\pi(x)}$, then what? In particular, if $\lambda = 0.525\log x/(\log\log x)$, then ...
1
vote
1answer
45 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
184 views
1
vote
1answer
54 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 ...
2
votes
2answers
151 views

How does one prove that $(2\uparrow\uparrow16)+1$ is composite?

Just to be clear, close observation will show that this is not the Fermat numbers. I was reading some things (link) when I came across the footnote on page 21, which states the following: $$F_1=2+1\...
2
votes
1answer
108 views

Constructing a smooth function whose roots consist only of each of the primes.

My first attempt: $$f(x) = \prod_{i=1}^\infty \left(1- \frac x {p_i} \right)$$ If we take a look at the Riemann zeta function: $$ \zeta(s) = \sum_{n = 1}^\infty \frac 1 {n^s} = \prod_{i = 0}^\infty ...
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
58 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
72 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
891 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
100 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
65 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
230 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
66 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
281 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
105 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
60 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
917 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 ...