Prime numbers are natural numbers 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
1answer
40 views

Prove that a is a primitive root mod p if and only if -a has order (p-1)/2

Consider a prime p $\in\mathbb{N}$ of the form 4t+3, with t $\in\mathbb{N}$. Prove that a$\in\mathbb{Z}$ is a primitive root mod p if and only if -a has order $\frac{(p-1)}{2}$. I showed most of the ...
3
votes
2answers
68 views

Number theory question about primes

I have a really interesting (and hard) number theory task: Prove, that every $p$ prime has a multiple(not $0$), which is smaller than $\frac{p^4}{4}$, and it can be written down as the sum of five ...
0
votes
0answers
20 views

Estimating the number of integers in a sequence of consecutive integers that are relatively prime to a given primorial

Let $x,y$ be positive integers and $p$ a prime. Is there a standard way to estimate the number of integers $z$ where $x \le z < x+y$ and $\gcd(z,p\#)=1$ For example, for $x=1000, y=30, p=7$, ...
2
votes
2answers
1k views

Prime powers that divide a factorial [duplicate]

If we have some prime $p$ and a natural number $k$, is there a formula for the largest natural number $n_k$ such that $p^{n_k} | k!$. This came up while doing an unrelated homework problem, but it is ...
6
votes
1answer
745 views

Prove that $(1+p)^{p^{n-1}} \equiv 1 \pmod{p^n}$ but $(1+p)^{p^{n-2}} \not\equiv 1\pmod{p^n}$, deduce $\text{ord}_{p^n}(p+1)=p^{n-1}$

I need some hints for this problem from Dummit and Foote. (edit: added the full question verbatim for context) Let $p$ be an odd prime and let $n$ be a positive integer. Use the binomial theorem to ...
0
votes
0answers
54 views

Why is $0$ the $0^\text{th}$ prime?

I found this question on $\prod_{n\to \infty}(1-1/p_n)$, played a little at Wolfram's Alpha and found the following: The series expansion of a related indefinite integral $\int \log (1-1/p_n)dn$ gave ...
1
vote
1answer
37 views

Is there numerical evidence supporting the predicted density of the primes of the form $x^2+1$?

A famous conjecture (due I think to Hardy and Littlewood) states that if $P(x)$ denotes the number of primes of the form $n^2+1$ less than or equal to $x$, then $$P(x)\sim \frac{C\sqrt x}{\log x}$$ ...
1
vote
2answers
41 views

Show that the sum of the products in pairs of the number 1,2,3…p-1 is divisible by p, where p is prime

If $p ≥ 5$ is prime, show that the sum of the products in pairs of the numbers $1, 2, . . . , p−1$ is divisble by p. We do not count $1×1$, and $1 × 2$ precludes $2 × 1$.
0
votes
0answers
27 views

Complete residue mod $p$ and number of solution to an equation

Prove that there are infinitely many primes $p$ such that the total number of solutions $\pmod{p}$ to the equation $3x^{3}+4y^{4}+5z^{3}-y^{4}z \equiv 0$ is $p^2$. I can show that for $p \equiv ...
0
votes
0answers
63 views

growth of the numbers $n$, such that $2n+1$ and $2n-1$ arent prime

I'm searching for upper and lower bounds and a "good" estimate for the function $f$ ($f[x] \sim x$ for $x\to+\infty$), which is counting the numbers $n\leq x$, s.t. $2n+1$ and $2n-1$ aren't prime ...
0
votes
1answer
30 views

Proof about prime numbers [duplicate]

Show that if $n$ is composite then there exists a prime $p \leq n^\frac{1}{2}$ such that $p\mid n$. I would like to use contradiction to prove this claim but I'm not sure about how I should ...
0
votes
1answer
63 views

all elements of ($Z$/p$Z$)* are cubes

Let $p$ be a prime An element $a \in$ ($Z$/p$Z$)* is called a cube if there exists $b \in$ ($Z$/p$Z$)* such that $a = b^3$ How to show that all elements of ($Z$/p$Z$)* are cubes ? And if $p \equiv ...
1
vote
1answer
55 views

Show that $1^m+2^m+\cdots+(p^2)^m\equiv-p\pmod{p^2}$ when $p-1\nmid m$

Can you please help of how can I approach this proof. I have seen a proof of the power sum of p in the internet but it doesn't seem very helpful. I want to show that $S_m(p^2)$ is congruent to $-p$ ...
0
votes
2answers
65 views

$\mathbb Z_p^*$ is a group iff $p$ is prime

I'm trying to prove $\mathbb Z_p^*$ is a group if and only if $p$ is prime. I know that if $p$ is prime $\mathbb Z_p^*$ is a group, but how can I do the converse? In another words, if the equation ...
0
votes
0answers
21 views

Find the number of solutions to the following congruence

Suppose that $N = p^a$, $gcd(c, p) = 1$, and that $p$ is an odd prime. $$x^e = c \pmod N$$ Prove that if any solution to the congruence exists, then there are exactly $gcd(e, p^{a}-p^{a−1})$ distinct ...
0
votes
0answers
45 views

find all primes $p$ such that $a^p-1$ has a primitive factor.

We say that a prime $q$ is a primitive factor of $a^n-1$ if $q|a^n-1$, but $q$ does not divide $a^m-1$ for any $m$ such that $0<m<n$. Given $a\ge2$, find all primes $p$ such that $a^p-1$ has a ...
28
votes
7answers
2k views

Are Mersenne prime exponents always odd?

I have been researching Mersenne primes so I can write a program that finds them. A Mersenne prime looks like $2^n-1$. When calculating them, I have noticed that the $n$ value always appears to be ...
4
votes
1answer
71 views

Are there infinitely many Thâbit ibn Kurrah cousin primes?

Positive integers of the form $3 * 2^n - 1$ are called Thâbit ibn Kurrah numbers. and if those numbers are prime they are called Thâbit ibn Kurrah primes. Now if for a fixed positive integer $n$ , ...
1
vote
2answers
74 views

Prove if, $2^n - 1$ is prime, then $n$ is prime. [duplicate]

Prove, when $n$ is a positive integer, if $2^n - 1$ is prime, then $n$ is prime. I did read some sort of proving on the web, but I could not understand it... Any help? And if possible, could the ...
0
votes
0answers
14 views

Help with Dixon's factorization algorithm?

I've been trying to implement Dixon's factorization method in python, and I'm a bit confused. I know that you need to give some bound $B$ and some number $N$ and search for numbers between ...
1
vote
0answers
54 views

Prime twins and $1 \mod 30$ confusion

Jie Wu improved Brun's theorem and showed that the number of prime twins up to $n$ satisfies for sufficiently large $n$ : $$\pi_2(n) < 4.5 \frac{n}{ln(n)^2} $$ However this confused me while ...
1
vote
1answer
25 views

Proof that Mersenne numbers with a composite exponent are also composite

I'm following the book The Haskell Road to Logic, Maths, and Programming, and I am unsure of one of my proofs for one of the exercises. It is to be proven that a number of the form $M_n = 2^n -1$ is ...
11
votes
3answers
295 views

Are there number systems or rings in which not every number is a product of primes?

I am reading through some number theory and abstract algebra books, and in the number theory books they all prove the theorem which states that every integer is a product of primes (irreducibles). In ...
8
votes
4answers
955 views

What exactly am I being asked in this question? I don't need the answer, just the interpretation.

Write a program that inputs a whole number N and outputs the percentage of relatively prime pairs of numbers a, b in the range 1 to N. For some reason, I'm having difficulty understanding the ...
0
votes
1answer
16 views

How many pickups $K$ should I do to have a $p$% of probability of picking up a divisor of $n$ (if exists) in the interval $[2..\lfloor n/2\rfloor]$?

I am trying to understand if it makes sense an algorithm to decide if a given number $n$ is possibly prime or not by using the divisor function bound defined by professor Jeffrey Lagarias as: ...
0
votes
0answers
52 views

A way to sum supernatural numbers involving Zeta function's analytic continuation

I have this idea on how to sum supernatural numbers assigning them a finite value in a way similar to how we assume that the sum of every natural numbers from 1 to infinity equals $-\frac 1 {12}$. ...
4
votes
1answer
32 views

$n>3$ be an odd integer , $k,t$ be smallest positive integers such that both $tn , kn+1$ are perfect squares . Then is $n$ prime iff $k,t>n/4$?

Let $n>3$ be an odd integer , $k,t$ be smallest positive integers such that both $tn , kn+1$ are perfect squares . Then is $n$ prime if and only if both $k,t$ are greater than $n/4$ ?
6
votes
3answers
74 views

Convergence of $\sum_{m\text{ is composite}}\frac{1}{m}$

It can be easily show that the harmonic series $$\sum_{n=1}^{\infty}\dfrac{1}{n}$$ is divergent. Also it has shown that the infinite series of reciprocals of primes $$\sum_{p\text{ is ...
2
votes
3answers
298 views

“Quadly” numbers with just 4 factors

A positive integer with exactly four positive factors is called "quadly". Compute the least $n$ for which each of $n,n+1$ and $n+2$ is quadly. (ARML 2008) My method of attacking this problem started ...
1
vote
0answers
72 views

Euclid's theorem: Paul Erdős's proof on the infinitude of primes

Seemingly simple question: Quote from Wikipedia: First note that every integer $n$ can be uniquely written as $rs^2$ where $r$ is square-free, or not divisible by any square numbers (let ...
3
votes
1answer
93 views

Under what operation prime numbers form a group?

After taking Modern Algebra I, I was wondering to find a group property among primes. It doesn't make sense. Does it? Anyways here is my first instance For any $p,q\in \mathscr{P}(prime)$ define ...
6
votes
3answers
3k views

Can Prime numbers be negative?

I was wondering, can a prime number be negative? We had a question over at security.se which stated that prime generation with openssl: openssl dhparam -text 1024 ...
1
vote
0answers
27 views

Maier's theorem

I have some questions with Maier's theorem https://en.wikipedia.org/wiki/Maier%27s_theorem If $1 < \lambda < 2$, then what? If $x+(\log x)^\lambda = x^{1+1/\pi(x)}$, then what? In particular, ...
-1
votes
2answers
61 views

Need a starter hint on python program. How do I start? [closed]

Write a program that inputs a whole number N and outputs the percentage of relatively prime pairs of numbers a, b in the range 1 to N. Can I use Euler's totient function?
0
votes
2answers
207 views

Number of solutions of arithmetic funtion's equation.

Say, an equation is given below \begin{equation} 2\pi(x) - \pi(2x)=\omega(x) \end{equation} where $x$ is a positive integer, $\pi(x)$ is the prime-counting function, and $\omega(x)$ is the number of ...
9
votes
1answer
72 views

How often is $1+\prod_{k=1}^n p_k$ not prime?

How often is $1+\prod_{k=1}^n p_k$ is not prime?,wkere $p_k$ is k'th prime consider that $2\times3\times5\times7\times11\times13+1=59\times509 = 30031$ is this one off or, are there infinitely many ...
3
votes
3answers
1k views

Random binary array shows patterns around prime numbers

First post, so please let me know if I'm doing something wrong or if this question does not belong here. I have been toying with java to visualize an interesting 2D binary array I thought of today in ...
2
votes
2answers
110 views

Even/Odd Binomial Coefficients

I was wondering if there's a nice general solution for the following problem: How many numbers in the $n^\text{th}$ row of Pascal's triangle are even? How many are odd?
21
votes
3answers
9k views

How many prime numbers are known?

Wikipedia says that the largest known prime number is $2^{43,112,609}-1$ and it has 12,978,189 digits. I keep running into this question/answer over and over, but I haven't been able to find how many ...
0
votes
1answer
40 views

improved segmented sieve of erastothenes complexity

I improved the segmented sieve of erastothenes , my algorithm doesnt repeat the multiples of primes using the equation $p^{2}_{n}p_{j}+2p_{n}p_{j} \times c =N$ wich shows when at least two multiples ...
7
votes
3answers
2k views

What would be the immediate implications of a formula for prime numbers?

What would be the immediate implications for Math (or sciences as a general) if someone developed a formula capable of generating every prime number progressively and perfectly, also able to prove (or ...
0
votes
0answers
27 views

Comparing a primorial $p\#$ to Dusart's upper bound for the $n$th prime

The number of elements of a reduced residue system modulo a primorial $p$ is $\varphi(p\#)$ I thought that it would be interesting to compare each primorial $p_i\#$ to the Dusart's estimate for the ...
51
votes
4answers
4k views
5
votes
4answers
229 views

Is there a conjecture with maximal prime gaps

Define $M_n$ to be the $n$th maximal gap between primes. That is, $M_1=1$ thanks to $3-2=1$; $M_2=2$ thanks to $5-3=2$; $M_3=4$ thanks to $11-7=4$; and in general, $M_n = p_{i+1}-p_i$, where $p_i$ is ...
4
votes
3answers
114 views

When is the number of $N$'s factors $1 + \sqrt{N}$?

(Answer: Only $N = 4$ and $N = 16$.) The following question arose in a course for pre-service and in-service elementary school teachers: For what $N \in \mathbb{N}$ is it the case that the ...
2
votes
1answer
73 views

Fifth root of an even number

Assume $x>1$ is an even integer, show that. $$\sqrt[5]{x} \notin \mathbb{N}$$ I am not sure if this is actually a true theorem, I am conjecturing based on $2, 4, 6, 8, 10, .... 126$. I am ...
10
votes
2answers
1k views

Who discovered the first explicit formula for the n-th prime?

I just found out on Wolfram that there is a formula for the n-th prime in terms of elementary functions. I wonder who found it and if he was rewarded for this. The formula (here) is: Also shown at ...
3
votes
1answer
35 views

What is the best estimate known for the upper bound for the difference between consecutive primes?

Bertrand's Postulate gives us that: $$p_n < p_{n+1} < 2p_n$$ So that: $$p_{n+1} - p_n < p_n$$ In this answer, this paper is cited which says in Prop 6.8 that: For $x \ge 396738$ ...
0
votes
0answers
78 views

Carmichael function and primitive roots of unity

I have been reading about the Carmichael function recently and I would like to ask about some elementary implication of its properties as I haven't found it stated explicitly. If I understand it ...
0
votes
1answer
31 views

Interesting pattern arises when plotting prime numbers on a Cartesian plane

While plotting prime numbers out of boredom one day, I stumbled upon an interesting pattern which may be expressed as such: Let $\mathbb{N}$ be the set of natural numbers. Let $\mathbb{P}$ be the set ...