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

66
votes
12answers
7k views

Why 1 is not considered to be a prime number?

Why $1$ is not considered to be a prime number? Or why definition of prime numbers is given for integers greater than $1$?
-2
votes
0answers
25 views

Connection between prime numbers and transcendental numbers

I think there may be a strong connection between prime numbers and transcendental numbers. I am unable to prove what I have in mind by myself, so I am seeking help. My hypothetic theorem would be: ...
-5
votes
0answers
40 views

Anyone can help me solve the big mathematics problem? [on hold]

Any one can find the roots : With any positive integers n, have one positive integers m greater than n: $m \neq 6xy+x+y $ $m \neq 6xy+x-y $ $m \neq 6xy-x-y$ with any positive integers $x,y $.
17
votes
0answers
78 views

Is there prime number of the form $0^1+1^2+2^3+3^4+4^5+…+(n-2)^{n-1}+(n-1)^n$?

Let A(n)= $0^1+1^2+2^3+3^4$....+$(n-2)^{n-1}+(n-1)^n$. So: A($1$)= $0^1$ A($2$)= $0^1+1^2$ A($3$)= $0^1+1^2+2^3$ A($4$)= $0^1+1^2+2^3+3^4$ and so on.... Is there prime number of such form?, ...
-2
votes
0answers
28 views

Supposed p is a prime Number such that (p-1)/4 and (p+1)/2 are also primes. Show that p=13

$p$ is not $2$ or $3$ (otherwise $\frac{(p-1)}{4}$ would not be an integer).Hence p must be an odd prime. Also $p-1$ is divisible by $4$ $p = 4t + 1$ (say) $\frac{(p-1)}{4}=t$ $\frac{(p+1)}{2}=2t$ ...
49
votes
5answers
5k views

Are there an infinite number of prime numbers where removing any number of digits leaves a prime?

Suppose for the purpose of this question that number $1$ is a prime number. Consider the prime number $311$. If we remove one $1$ from the number we arrive at the number $31$ which is also prime. If ...
2
votes
4answers
85 views

Should we or should we not take $1$ as a prime number? [duplicate]

I think I know that there were times in the past when it was convenient to look at a number $1$ as a prime number, and, as far as I can remember, even then it was dependent on who we ask is it prime ...
11
votes
3answers
118 views

Why is the Fundamental Theorem of Arithmetic so important?

I've recently read about the Fundamental Theorem of Arithmetic and I think that I have just about understood the proof. What I found quite interesting at first was the "Fundamental" part in the name. ...
3
votes
0answers
32 views

Why do we know that , besides the known idoneal numbers , there is at most one more?

Here https://en.wikipedia.org/wiki/Idoneal_number the definition of an idoneal number is given : A number $n$ is idoneal if there are no integers $a,b,c$ with $0<a<b<c$ and $n=ab+ac+bc$ A ...
1
vote
1answer
51 views

Let $P$ be a prime. Show that $\exists$ $x \in \mathbb{N}$ such that $f(x) = p$ then $\exists$ $y \in \mathbb{N}$ such that $g(y) = p$

What is given? $$\text{Let P be a prime}$$ $$\text{Let} \space f(x)= 3x+1$$ $$\text{Let} \space g(x)= 6x+1$$ Show that: If there exists $x \in \mathbb{N}$ such that $f(x) = P $ , then there exists a ...
1
vote
1answer
30 views

Prove that $\sum^{P}_{k=1} \lfloor\frac {ka}{p}\rfloor = \frac{p^{2} - 1}{8} + \mu(a,p)$ mod$(2)$

I can prove that $\sum^{P}_{k=1} \lfloor\frac {ka}{p}\rfloor = \mu(a,p)$ mod$(2)$ where $p$ is an odd prime, $P = \frac {p-1}{2}$, $a$ is an integer not divisible by $p$, and $\mu(a,p)$ is the ...
1
vote
1answer
30 views

Prove $∑^{(p−1)/2}_{k=1} \left \lfloor{\frac{2ak}{p}}\right \rfloor \equiv ∑^{(p−1)/2}_{k=1} \left \lfloor{\frac{ak}{p}}\right \rfloor ($mod $2)$

If $p$ is an odd prime number and $a$ is an odd integer not divisible by $p$, then why does $∑^{(p−1)/2}_{k=1} \left \lfloor{\frac{2ak}{p}}\right \rfloor \equiv ∑^{(p−1)/2}_{k=1} \left ...
1
vote
1answer
28 views

The prime counting function has a lower bound of $C\log\log x$

I read that using Euclid's Theorem and by induction, a "gross underestimation" of the Prime Counting Function $\pi(x)$ can be stated as $C \log \log X$, i.e there is a constant $C$ such that the ...
-2
votes
1answer
35 views

Divisibility by 11 [on hold]

$xyzw$ is a 4 digit number such that x is even,y is smallest possible odd number,z is greatest prime no,w is a multiple of 3.if ($xyzw + n$) is divisible by 11 then n cannot be: a. 6711 ...
2
votes
1answer
43 views

If $0 < a < b,$ there exists an $x_{0}$ such that for $x \geq x_0$ there is at least one prime between $ax$ and $bx.$

My approach: I first showed that for $0 < a < b,~\pi(ax) < \pi(bx)$ if $x \geq x_{0}.$ Now, since $\pi$ is an integer valued function, $\pi(bx) - \pi(ax) \geq 1$ for all $x \geq x_0.$ i.e. ...
6
votes
1answer
53 views

Can we find prime numbers with any sum of digits (except those divisible by three)

I guess that this question is not something new and that there must be people who wanted to know if this question has an affirmative answer, but I would like to share it with you, because I really do ...
2
votes
0answers
23 views

Summing the digits of sum of the digits to obtain prime numbers

Define sum of digits (in base $10$) function as $sd_{10}(n)=\sum_{i=0}^ma_i$ where $n=\sum_{i=0}^ma_i \cdot 10^i$ and $0\le a_i\le 9$. If we choose prime number $86423$ and sum its digits we obtain a ...
4
votes
1answer
43 views

Fractions of powers of primes.

I'm wondering whether the following statement is true: Let $p$ and $q$ be two prime numbers (or more generally let $p$ and $q\neq 0$ be integers with $\gcd(p,q)=1$). Then for all $\varepsilon >0$ ...
8
votes
3answers
10k views

Fastest prime generating algorithm

What is the fastest known algorithm that generates all distinct prime numbers less than n? Is it faster than Sieve of Atkin?
1
vote
2answers
30 views

Sum of reciprocals of prime-index-primes

Let $p_1=2$, $p_2=3$, $p_3=5$, $\ldots$ be an enumeration the prime numbers. If $q$ is a prime number, we call $p_q$ a prime-index-prime. A list of prime-index-primes can be found here. My question ...
5
votes
1answer
103 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: ...
0
votes
0answers
35 views

For a prime p and a positive integer n

we define $A_{p,n} = \{(x,r) : 1 \leq x \leq n \textrm{, r is a positive integer, } p^{r} \textrm{divides x} \}$. Describe the set $A_{p,n}$ for p=5 , n=100. Does the set comprise of ...
13
votes
3answers
706 views

Can second degree polynomials generate as many as we wish prime numbers in the way described?

While I was getting in my pyjamas, a few minutes ago, the Euler polynomial $n^2+n+41$ came into my mind. As you know, this polynomial is famous because the set $\{f(0),f(1),...f(39)\}$ consists of ...
3
votes
3answers
44 views

Does the PNT establish a connection between primes and the logarithm?

The prime number theorem states that $$\pi(x) \sim \frac x {\ln(x)}$$ Morally, this seems to suggest that there is a fundamental connection between primes and the natural logarithm. But since we're ...
26
votes
4answers
5k views

Primes of the form $n^2+1$ - hard?

I met a student that is trying to prove for fun that there are infinitely many primes of the form $n^2+1$. I tried to tell him it's a hard problem, but I lack references. Is there a paper/book ...
0
votes
0answers
84 views

An equation which generates all primes within a specific range

Does there exist an equation which generates all primes within a specific range like 10 to 100 ? If I discover one such kind of equation, will it be a good discovery ?
-1
votes
0answers
79 views

“Matrix sieve” - primes finding algorithm - is it useful for number theory? [closed]

I proposed "matrix sieve" algorithm for finding primes that in my opinion is simple, not needed operations of dividing and easy to memorize: In order to find all primes (up to a given limit) in the ...
3
votes
2answers
254 views

How to understand Apostol's proof of the irrationality of $\sqrt{n}$ if $n$ is not a perfect square?

Recently I am reading the textbook of Apostol, Mathematical Analysis, Second Edition. On page 7, there is a theorem 1.10: If $n$ is a positive integer with is not a perfect square, then $\sqrt{n}$ is ...
5
votes
4answers
59 views

Total number of integers relatively prime to $p^2$

I am reading my number theory textbook and it states without proof that the total number of elements relatively prime to $p^2$ for some prime $p$ is $p(p-1)$. Why is this so? I know that the number of ...
1
vote
2answers
65 views

Without calculating them determine whether $36^2+1$ and $154^2+1$ are prime and find the prime factors if not prime

I know that $36^2 + 1$ is prime, $154^2 + 1$ is not, both are equal to $1 \bmod 4$. The prime divisors of $154^2 + 1$ should also be of the form $1 \bmod 4$. Tried showing this by Wilson's theorem ...
2
votes
1answer
33 views

Is it always true, for a prime $p$, a generator $g$ of $\mathbb{Z}^*_p$ cannot be a quadratic residue modulo $p$?

Let $p$ be a prime, then is it true that a generator $g$ of $\mathbb{Z}^*_p$ cannot be a quadratic residue modulo $p$? And if yes why?
6
votes
1answer
133 views

Why can this cosine sum function show all primes less than $N^2$?

I constructed this cosine sum that puts all primes within N on line y=1, and its zeros show the sieve by primes less than N. For $x<N^2$, they are all primes. $$ ...
4
votes
1answer
46 views

How can I find the $n^{th}$ 'reversible prime'?

I just thought of an interesting problem when discussing prime numbers with a friend. Some numbers are prime, but even fewer numbers preserve their primality when we reverse their digits. So for ...
0
votes
2answers
45 views

Totien-Sum: why GCD( {n}/d, q/d) = 1; implies Sum{Totient(d/q) } = q

Have seen answer to this question. still don't understand.. Totient sum is defined: q = Sum(Totient (d) ); sum on all d : d|q More specific; The proof has these steps: 1. If d is a divider ...
0
votes
1answer
18 views

Find a unique value for $d$ in $(d \cdot e) \pmod{F} \equiv 1$

Given that I know the value of $e$ and $F$. How to determine an unique integer value for $d$ in such a way that the reminder of the division of $(d \cdot e)$ per $F$ is equal to one? $(d \cdot e) ...
2
votes
1answer
20 views

Half primes in the set

Let S be 30 element subset of {1,2,....2015} such that every pair of elements in S are relatively prime. Prove that at least half of the elements in S are prime numbers
3
votes
1answer
38 views

Solving $(ap)^2-d(bq)^2=1$ for distinct primes $p,q$

I'm pondering the following claim regarding special cases of the Pell equation. Conjecture: For every pair of distinct primes $p$ and $q$, there exist integers $a$ and $b$, and a non-square integer ...
3
votes
0answers
277 views

The Divisors of $s(2s+1)$ and Primes $2n+1$ and $3n+1$ part 1

I want to check my math (and proof) on the following claim. The claim is by way of a computer search and a "hunch". claim: If $s$ is a prime number I write $\varphi_{s} =s(2s+1)$. Let $\tau$ be ...
1
vote
1answer
37 views

Number theory, prove that a prime number $p \mid 1$

Consider a prime number $p > 1$ and $a \in \mathbb{Z}$ and $p < a$. We know $p \mid a$, then $a = p.b$ for $b \in \mathbb{N}$. We also already know the congruence $a \equiv 1 (\text{mod } m)$ ...
9
votes
2answers
187 views

Numbers of the form $(p_{1}^{\alpha_{_{_1}}})^{2}+(p_{2}^{\alpha_{_{_2}}})^{2}+\cdots+(p_{n}^{\alpha_{_{_n}}})^{2}=(p_{m}^{\alpha_{_{_m}}})^{2}$

I'm looking for numbers of the form $$(p_{1}^{\alpha_{_{_1}}})^{2}+(p_{2}^{\alpha_{_{_2}}})^{2}+\cdots+(p_{n}^{\alpha_{_{_n}}})^{2}=(p_{m}^{\alpha_{_{_m}}})^{2}$$ where $p_{i}$ are prime numbers, ...
0
votes
0answers
30 views

Is it possible to count primes using a regression model?

Let $Y$ equal the number of primes less than a value $X$. Given the equation: $Y =Ax^B + C$ Where $A$ is a regression coefficient, $B$ is some exponent and $C$ is an error term, can one estimate ...
1
vote
1answer
62 views

Factoring semiprimes cost estimation

I have two problems that are the following. The first problem is the following: I need to estimate the cost of factorizing a given semiprime based on previous estimations. For example I have the time ...
3
votes
1answer
48 views

If $p_n$ is the $n^{th}$ prime, is it ever appropriate to speak of $p_{\aleph_0}$?

If $p_n$ is the $n^{th}$ prime, is it ever appropriate to speak of $p_{\aleph_0}$? I'm no math student. Your pardon if this is just some clearly obvious and easy answer, I'm just not seeing it. ...
5
votes
1answer
57 views

Would such a function be of any importance (primality test)?

While experimenting with some Maths, I came up with a really cool function. Let's call this function $\space \beta \space$. Which is a function of a real variable $\space r \space $. Here is the ...
0
votes
1answer
24 views

Calculate Euler inverse function

Given $n$ find all values n such that: $\phi(n) = 26$. I've searched over the web and I've managed to find the lower and upper bounds for n, but i don't know how to go on from this point. I'll be ...
0
votes
0answers
29 views

N as sum of k primes [closed]

How can we say if N can be represented as a sum of k prime numbers .If N=10 and k=2 it can be represented as sum of two primes (5+5) .How can we say this for any N and K .
2
votes
1answer
84 views

Prove that $\prod\limits_{2 < p \leq y}\left(1-\frac{2}{p}\right)\sim\frac{D}{\log ^2 y}$ [duplicate]

I'm writing my bachelor thesis about Brun's sieve method and his theorem. In one proof I found this statement without further explanation. It is important to show that the product doesn't converge ...
0
votes
0answers
29 views

Finding pseudoprimes using differences of prime products

Using the first nine primes $(2,3,5,7,11,13,17,19,23)$, what is the smallest (2nd smallest if $1$ is possible) difference that can be created using products of these primes? Rules are as ...
1
vote
1answer
44 views

Primality testing vs sieve

If the goal is to decompose an integer into its prime factors, is it better to use a sieve (such as the Sieve of Eratosthenes) or trial division up to the square root? Wikipedia has the statement ...
1
vote
5answers
52 views

Then there exists a unique natural number $b$ less than $p$ such that $ab \equiv 1 \pmod{p}$. [duplicate]

Full question: Let $p$ be a prime and let $a$ be an integer such that $1 \leq a < p$. Then there exists a unique natural number $b$ less than $p$ such that $ab \equiv 1 \pmod{p}$. Looking for the ...