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

44
votes
12answers
6k views

Proof that every number ≥ $8$ can be represented by a sum of fives and threes.

Can you check if my proof is right? Theorem. $\forall x\geq8, x$ can be represented by $5a + 3b$ where $a,b \in \mathbb{N}$. Base case(s): $x=8 = 3\cdot1 + 5\cdot1 \quad \checkmark\\ x=9 = 3\cdot3 ...
0
votes
1answer
37 views

change the order of the digits of a prime number

What is prime numbers called, that if you arbitrary change the order of its digits, you will only get another prime number. For example 79 (79 is prime number as well 97) or 199 (199, 919, 991 is ...
2
votes
2answers
52 views

If $n$ is a positive integer such that $2^n+n^2$ is a prime number , then is it true that $6|n-3$ ?

If $n$ is a positive integer such that $2^n+n^2$ is a prime number , then is it true that $6|n-3$ ? Trivially $n$ cannot be even , so this leaves us only with the possibilities $n \equiv1,3,5( \mod 6) ...
1
vote
3answers
124 views

Solve $x^p + y^p = p^z$ when $p$ is prime

Find the solutions in positive integers of $x^p + y^p = p^z$, where $p$ is a prime number. Particular case $p=2$: For $z=0$ there are no solutions. For $z=1$ the only solution is $x=y=1$. For ...
0
votes
1answer
18 views

Relation between LCM of terms of sequence with sum of sequence

Is there any relation between LCM of some arbitrary sequence and sum of elements of sequence ? How to find the LCM if only sequence sum is given in short time ?
0
votes
0answers
26 views

How to get a prime $p$ such that $kp$ for any $k \in \mathbb{Z}$ does not equal to $ar - b$ where $r,b$ given and $a \in \mathbb{Z}$

Suppose that $R$ is a finite set of positive natural numbers given. Let $r \in R$. $b$ is the product of numbers in $R$. We want to select a prime $p$ such that for every $r$, $ar - b \neq kp$ where ...
2
votes
1answer
112 views

Solutions to $y^2 = x^3 + k$?

As you know, the equation $y^2 = x^3 + k$ for $k = (4n-1)^3 - 4m^2$, with $m, n \in \mathbb{N}$ and no prime number that p is congruent to 1 modulo 4 count m, don't have any answer and its proof can ...
10
votes
1answer
75 views

Is there a natural number for which all the sums and differences of its factor pairs are prime?

The 8 factor pairs of e.g. 462 are $((1, 462), (2, 231), (3, 154), (6, 77), (7, 66), (11, 42), (14, 33), (21, 22))$. Of the 16 non-negative integers which are the sums and differences of these pairs ...
0
votes
2answers
81 views

If a prime $p\mid b$ and $a^2=b^3$, then $p^3\mid a$

I have an exercise that I don't know how to solve. I tried to solve it in many ways, but I didn't get any progress in proving or disproving this... The exercise is: Prove or disprove: if $p$ is a ...
3
votes
2answers
55 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 :)
3
votes
1answer
39 views

Prove about prime numbers obtained from certain sums of squares of an integer $n$

I would like to ask for a prove about an observation I did regarding the sums of squares and prime numbers (in another question here), or a counterexample of it. My capabilities to do this kind of ...
0
votes
0answers
44 views

Prime pairs $(p,q)$,$\quad q=(n \quad mod \quad p)$ and $2p+q=n (odd)$. Is there a definition about them?

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
1answer
23 views

Vanishing property of logarithmic derivative of zeta function

I was trying to derive the explicit formula for the integrated Chebyshev $\psi$ function, $\psi_1$ defined as \begin{equation}\psi_1(x)=\int_1^x\psi(y)dy\end{equation} But I have stumbled upon one ...
1
vote
2answers
65 views

Form of a prime dividing a certain difference of two prime powers.

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$.
0
votes
1answer
49 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$ $\pmod{p}$. I think this can be done by viewing the primitive roots as a elements of ...
-1
votes
1answer
46 views

find a formula for $S(n)$ [closed]

Let $S(n) =\sum\tau(d)\sigma^2(d)$, where the sum is taken over all divisors $d$ of $n$. How to find a formula for $S(n)$ in terms of the prime factorization of $n$?
1
vote
2answers
63 views

Number of distinct prime divisors of an integer $n$ is $O(\log n/\log\log n)$

I strongly believe that the claim is true; but I'm neither a mathematician nor speaking French and hope that somebody can confirm it, since related questions (here, here and here) either don't have an ...
-2
votes
2answers
81 views

How to check if $2$ is a square $\mod 3$?

I don't think I can use the Legendre or Jacobi symbol here because $2$ is an even prime. I'm not sure I've learned methods to deal with $2$ even though I know how to use quadratic reciprocity, it only ...
38
votes
1answer
1k views

Estimate for $n$th prime

A good approximation I have found for $p_{n}$ is \begin{align} \int_{2}^{n}\log (x \log (x \log (x)))\ dx\\ \end{align} and seems to be a better estimate than $n \log (n)$. The error term seems to ...
0
votes
1answer
35 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
65 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
18 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
742 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
53 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
39 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
62 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
votes
2answers
63 views
1
vote
1answer
54 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
20 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
71 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
11 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
52 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
24 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
290 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
50 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
31 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
72 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 ...
1
vote
3answers
296 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
70 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 ...