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

1
vote
1answer
31 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
44 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
56 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 ...
5
votes
1answer
45 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
39 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
108 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
36 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
718 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
46 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 ?
3
votes
2answers
259 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
60 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
67 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
34 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?
7
votes
1answer
147 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
48 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
48 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
19 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
27 views

Half primes in the set [closed]

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
39 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
280 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
32 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
63 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
52 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
26 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 ...
2
votes
1answer
88 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
46 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
53 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 ...
-1
votes
2answers
81 views

Is this definition of Mersenne Primes correct? [closed]

According to my understanding, the definition of Mersenne Prime is the following: A Mersenne Prime is a prime number that is obtained by using the formula $2^n-1$, where $n\in\mathbb{N}_+$
1
vote
0answers
31 views

Help understanding one of Euler's theorem in Number Theory [duplicate]

I am looking at two Euler's theorems in my textbook which are the following: If $p$ is prime and $a$ is any whole number, then $(a+1)^p - (a^p + 1) $ is evenly divisible by $p$. If $p$ is prime and ...
28
votes
7answers
3k views

Can a complex number be prime?

I've been pondering over this question since a very long time. If a complex number can be prime then which parts of the complex number needs to be prime for the whole complex number to be prime.
6
votes
0answers
267 views

Complex prime numbers

I was just learning about how, if you multiply any two complex numbers together, you get a new complex number. With that in mind, is there such a thing as complex numbers that cannot be factored, or ...
12
votes
3answers
2k views

What is wrong with this proposed proof of the twin prime conjecture?

I was thinking on the twin prime conjecture, that there are an infinite number of twin primes... I came up with a proof. I have to think that it is incomplete or wrong, because many great minds ...
7
votes
1answer
116 views

Are there any known special properties of a number located between twin primes?

With the exception of $4$, every number located between twin primes is divisible by $6$. This one is obvious, but are there any other properties that can be ascribed to such numbers? A property may ...
1
vote
1answer
43 views

Prime conjecture containing primorial

Help me find the exact conjecture statement. What I roughly remember is that it stated that the difference between primorial $n\#$ (product of first $n$ primes) and "some" larger number than the ...
71
votes
2answers
8k views

The square roots of different primes are linearly independent over the field of rationals

I need to find a way of proving that the square roots of a finite set of different primes are linearly independent over the field of rationals. I've tried to solve the problem using ...
1
vote
0answers
43 views

simplifying a sum with modular arithmetic

Let $p\!\geq\!3$ be a prime and $n\!\in\!\mathbb{N}$. For $i\!=\!1,\ldots,n$ let $w_i\!=\!2i\!-\!n\!-\!1$. Let $n\%p$ denote the remainder in the integer division of $n$ by $p$. Can the following sum ...
1
vote
1answer
34 views

Fermat's little theorem's proof for a negative integer

I'm in the process of proving Fermat's little theorem. For a prime integers $p$ we have $a^p \equiv a \mod{p}$ I proved it for a non-negative $a$, not I need to generalize the case to an ...
0
votes
0answers
22 views

Proving that ${p \choose r}$ is an integer for a prime $p$ and $0 < r < p, r \in \mathbb{Z}$ [duplicate]

I need to prove that given integers $p$ and $r$ such that $p$ is prime and $0 < r < p$, ${p \choose r} = \frac{p!}{r!(p-r)!} \in \mathbb{Z}$ As of now, I don't have any ideas on how to proceed. ...
0
votes
0answers
49 views

Concatenating the first n semiprimes (in order) to get a semiprime $469101415$…

The concatenation of the first $1,2,3,6,43$, and $61$ semiprimes (in order) is a semiprime (!), $4=2 . 2$ $46=2 . 23$ $469=7 . 67$ $469101415=5 . 93820283$ $4691014152122....121122123129$ (proven ...
2
votes
1answer
24 views

proof of condition of irrationality

I want to find a proof of the fact that $a^b$ is irrational if $a$ is a prime and $b$ is not an integer. Motivation behind this question: I was posed a question , of finding what is the probability of ...
0
votes
1answer
24 views

Question about equations involving sum of powers modulo a prime

After reading an article by Peter Norvig about Beal's Conjecture I became pretty interested in digging into it. In his article here he goes into the use of a technique to optimize checking by this: ...