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
0answers
7 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 ...
1
vote
1answer
29 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}$$ ...
0
votes
2answers
26 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$.
2
votes
1answer
37 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
1answer
27 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
47 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 ...
2
votes
2answers
47 views

If p is an odd prime then prime divisors of $(2^p-1)$ [duplicate]

If $p$ is an odd prime Prove that the prime divisors of $(2^p-1)$ are of the form $(2rp+1)$.
1
vote
2answers
55 views

p and q are odd primes then Solve for below

Let p and q be odd primes. If $q$ | $(a^p-1)$ then, either $q$ | $(a-1)$ or $q=(2rp+1)$ for some integer $r$.
1
vote
1answer
27 views

Product of Distinct Primitive roots

Let $p$ be an odd prime. Show that the product of the distinct primitive roots $mod$ $p$ is $\equiv$ $1$ or $-1$ ($mod$ $p$). I think this can be done by If we view the primitive roots as a ...
1
vote
2answers
67 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
10 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
44 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
20 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 ...
0
votes
1answer
54 views

Conjecture on Prime Numbers. [on hold]

Conjecture 1. Being $P$ the product of the multiplication of several different prime numbers, and being $N_p <P$ any prime number not being prime factor of $P$; being $N_L < │P^{1/2}│$ any prime ...
0
votes
1answer
14 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: ...
2
votes
1answer
63 views

$\lim_{n\to\infty}\left(\frac{\log(p_{n+1})}{\log(p_n)}\right)^n = C?$

There is a conjecture (which is weaker) related conjecture to Firoozbakht's conjecture (see OEIS A182514 Commments) which states (and define $L$): $$L := \left(\frac{\log(p_{n+1})}{\log(p_n)}\right)^n ...
4
votes
1answer
58 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$ , ...
0
votes
0answers
41 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}$. ...
6
votes
3answers
69 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 ...
4
votes
1answer
28 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$ ?
11
votes
3answers
271 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 ...
0
votes
0answers
58 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 ...
2
votes
1answer
83 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 ...
1
vote
0answers
72 views

How to determine if a number is product of exactly two primes? [on hold]

Suppose $X = p_1p_2$ where $p_1$ and $p_2$ are (not necessarily consecutive) prime numbers. Given $X$, what are the different ways to prove or determine that $X$ is a product of two primes? We ...
0
votes
2answers
32 views

How to decide the randomness of a dataset by checking the prime numbers inside it?

So it is weekend! I am reading currently a book where I found this sentence: "71 percent of men said they had a 'good sense of direction'. Only 47 percent of women reported same thing.", and I thought ...
1
vote
0answers
25 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
54 views

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

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
0answers
63 views

goldbach`s conjecture remark [on hold]

Goldbach`s conjecture states that every even integer greater than 2 can be expressed as the sum of two primes. Since every odd composite number is expressed as $p^{2}_{n}+ 2p_{n} \times c =N$ with ...
8
votes
4answers
947 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 ...
1
vote
1answer
163 views

An equation of prime counting function.

I have encountered the below problem- Given, $z(z-1)$ is divisible by all prime(all prime factors of $z(z-1)$ are consecutive) < $\sqrt{z} <n$ , Prove(or ...
2
votes
1answer
37 views

Find prime numbers $p,q$ such that: $pq| p^p+q^q+1$

Le $p,q$ be prime numbers such that: $pq| p^p+q^q+1$ Find $p,q$ I don't have any ideas about this problem :( Thanks :)
0
votes
0answers
35 views

$(p,q)$,$\quad q=(n \quad mod \quad p)$ and $2p+q=n (odd)$. Are they studied?

I am studying congruences and I have observed this kind of prime pairs $(p,q)$ related to odd numbers. Do this kind of prime pairs have a name or have been studied before? Here is the definition: ...
0
votes
0answers
24 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 ...
0
votes
1answer
34 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 ...
0
votes
0answers
42 views

Is there any real world application for simplifying roots? [closed]

I am someone who graduated college at the end of last year, and am now working in IT Security. After nerding out over cryptography with my boss, talking about RSA encryption's usage of factoring ...
3
votes
1answer
31 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$ ...
9
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 ...
0
votes
1answer
26 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 ...
4
votes
0answers
30 views

Relationship between Mersenne Primes and Triangular / Perfect Numbers

I'm a new user and have only a college sophomore's understanding of mathematics, so please bear with me. I was reading a book titled “The Simpsons and their Mathematical Secrets” in which the author ...
2
votes
1answer
71 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 ...
0
votes
0answers
53 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 ...
2
votes
0answers
60 views

Is there a strong version of twin prime conjecture?

The twin prime conjecture states that : There exists infinitely many integers such that $n$ and $n+2$ are both primes for a fixed $k$, can we find integers $a_1,a_2,\cdots, a_k$ such that: ...
1
vote
1answer
41 views

What is a good example of an algorithm that is hard to parallelise?

When I have 10 computers, the factorization of a number doesn't scale along. I am not sure how much faster it would go compared to a single computer, but not 10 times faster like one would expect. ...
3
votes
0answers
155 views

Primality Test for $N=2\cdot 3^n-1$

Definition 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 . Conjecture Let $N=2\cdot 3^n-1$ such ...
5
votes
5answers
68 views

If $p$ is a prime integer, prove that $p$ is a divisor of $\binom p i$ for $0 < i < p$

I was thinking of using the definition for combinations and use the fact that $p$ appears in the expansion of $\binom pi$ and hence $p$ is a divisor. I don't know whether I am on the right track!
-2
votes
2answers
56 views

find all pair of primes such that $p+q=18(p-q)$ [closed]

Find all pair of primes such that $p+q=18(p-q)$ Please Justify the answer.
4
votes
1answer
58 views

Sum and Product Puzzle and Prime Factors

Suppose we have two number $X$ and $Y,$ such that $1 < X < Y < 100,$ and $X + Y ≤ 100.$ Sue is given $S = X + Y$ and Pete is given $P = XY.$ They then have the following conversation: ...
3
votes
1answer
40 views

Prove that $\langle S\rangle$ $= G$, with $S \subset G$ and #$S > 1/p $ #$G$

I'm having trouble with solving this problem: Let $G$ be a finite group of order $> 1$, and $S \subset G$ a subset of $G$, with #$S > 1/p $ #$G$ Where p is the smallest prime factor of the ...
-2
votes
0answers
52 views

primes finding algorithm complexity?

I developed a prime finding algorithm using the equation $k=p^{2}+2p\times c$ with $k$ is an odd composite and $c$ is a constant $\in Z^{+}$. The algorithm eliminates only the odd composite and ...
6
votes
3answers
99 views

Find all prime numbers p such that both numbers $4p^2+1$ and $6p^2+1$ are prime numbers?

I tried $p$ for $2, 3$ and $5$ and they are not primes for both cases. How can I find all these prime numbers that satisfy those conditions?