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

prove that for every integer $a>0$ there is a unique representation $a=r*s^2$ [duplicate]

I need to prove that for every integer $a>0$ there is a unique representation $a=r*s^2$ where $r$ is not dividable by any square: there is no $d>1$ such that $d^2|r$ What I tried is to show a ...
1
vote
2answers
54 views

show that $\lim(\pi(x)/x) = 0$

I need to show that: $$\lim_{x\to\infty}(\pi(x)/x) = 0$$ Where $\pi(x)$ is the number of primes smaller then $x$. I tried using the fact that: $$\pi(x)<(1-1/2)(1-1/3)...(1-1/k)X + O(1)$$ but ...
3
votes
2answers
46 views

Proving infintely many primes of the form 6k-1

I have seen the past threads but I think I have another proof, though am not entirely convinced. Suppose there are only finitely many primes $p_1, ..., p_n$ of the form $6k-1$ and then consider the ...
7
votes
3answers
575 views

Proof of Wolstenholme's theorem

According to the theorem, if $$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\cdots+\frac{1}{p-1} =\frac{r}{q}$$ then we have to prove that $r\equiv0 \pmod{p^2}$. (Given $p>3$, otherwise ...
0
votes
0answers
51 views

What is this pattern in this calculation using primes?

So i was bored and when i get bored i write small programs that calculate something. This time i did this: I searched for the amount of primes bellow 10,000,000 using Sieve of Eratosthenes starting ...
1
vote
1answer
42 views

How n (1+b) is not prime?

Here is the complete proof taken from this link How do I convince myself that n(1+b) is not prime when b>=1? Here is what I did: if n is 3 and b is 3. Then ...
16
votes
4answers
792 views

Mapping natural numbers into prime-exponents space

Take any natural number $n$, and factor it as $n=2^{e_1} 3^{e_2} 5^{e_3} ... p^{e_i}$, where $i$ is the $i$-th prime. Now map $n$ to the point $n \mapsto (e_1,e_2,\ldots,e_i,0,\ldots)$, where $i$ is ...
-1
votes
1answer
36 views

Help on understanding this congruency

It is really simple but somehow I cannot connect the dots. If $p$ is an odd prime, how come $-1 \not\equiv 1 \pmod p$ ?
3
votes
1answer
57 views

Are some Lucas numbers always coprime with all previous Lucas numbers?

I was looking at this webpage which lists the first 200 Lucas Numbers color-coded with their prime factors and I noticed that all the Lucas numbers with power of two or prime indexes were relatively ...
1
vote
2answers
28 views

Finding the upper bound for a number's factors length

Okay, so the title is a bit misleading but I had to keep it short.. Anyhow, if I have a number X what will the length of it's longest two factors be? For example: $X = 10000$ I want $3$ and $3$ ...
0
votes
0answers
18 views

If :$\sum_{k=1}^{n}k^p =(\frac{n(n+1)}{2})\mod(p)$ how i deduce the remain of :$\sum_{k=1}^{n}k^{-p}$?

I have tried to determine the remain of this serie:$\sum_{k=1}^{n}k^p$ : I got this formula $\sum_{k=1}^{n}k^p =(\frac{n(n+1)}{2})\mod(p)$ ,where $p$ is prime and $k$ is positive integer .Now ...
13
votes
3answers
199 views

If $p$ is a prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

The proof is already given in the textbook but I tried other way around. Proof by contradiction: Let's assume that $p$ doesn't divide $a$ and $p$ doesn't divide $b$, but $p$ divides $ab$. So ...
2
votes
2answers
52 views

Why are there at most $n-1$ positive roots for polynomials with prime powers?

I was attempting to solve this old contest math problem posted Show that a matrix has positive determinant yesterday and I realize that I don't even know why the hint provided is true. From that ...
0
votes
0answers
15 views

Pairwise relatively prime terms of a polynomial.

Suppose we have a polynomial $P(n)$ (with degree $\geq 2$) with integer coefficients and a positive leading coefficient. Is it true that there is a $n_0\in \mathbb{N}$ with the property: For every ...
6
votes
2answers
306 views

Proving that a “prime graph” is connected

Let the prime graph be defined as the graph of all natural numbers, with two vertices being connected if the sum of the numbers on the two vertices add up to a prime number. Prove that the prime ...
4
votes
0answers
68 views

Probability and sums of prime factors

Of the first $N$ natural numbers, we select two different numbers at random. We'll call the greater one $A$ and the lesser one $B$. What is the probability $P$ that the sum of $A$'s prime factors is ...
1
vote
1answer
38 views

polynomial with nonzero coefficients at prime degree terms

Let $P(x)$ be a polynomial with integer coefficients. Show that there is a non-zero polynomial $Q(x)$ with integer coefficients, such that the product $$P(x)Q(x)=\sum_{k\ge 0}a_k x^k$$ has only ...
3
votes
1answer
29 views

Why is Newman's Analytic Theorem neccessary

In a proof of the prime number theorem along the lines of Newman's, we establish that $-\frac {\zeta'(s)}{\zeta(s)}-\frac 1{s-1}$ possesses an analytic continuation to $\Re(s)\ge 1$ and that ...
2
votes
1answer
25 views

Finding a bound on double summation involving primes

I am reading a number theory proof of a result in which I am stuck on a bound.Suppose $p_1$ and $p_2$ are primes with the property that each $p_i$ satisfies $e^r \leq P_i <e^{r+1}$ and $P_1 \equiv ...
6
votes
0answers
203 views

Relatives of Heegner numbers?

It is well known that Euler's lucky numbers are related to the Heegner numbers, where \begin{align} &n^2+n+p\\ \end{align} gives primes for $n=0,\dots,p-2$ if and only if its discriminant ...
1
vote
2answers
37 views

If all pairs of addends that sum up to $N$ are coprime, then $N$ is prime.

I think this must be a known theorem, but I've tried searching for it on google without much luck. I would state it as follows: If for all possible pairs of addends that sum to the same number N ...
4
votes
2answers
111 views

Help with deriving an absolute strategy (very fun if anything)

My friend and I are trying to figure out a solution or even a best path to figuring out a certain win strategy to this game. This game that my friend made, calling it the number game for short, is ...
0
votes
1answer
36 views

The number of consecutive odd integers whose sum can be expressed as $50^2-13^2$

Here i have a question that To find the number of consecutive odd integers whose sum can be expressed as $50^2-13^2$ Just i am unable to understand the question what is really it is asking. Please ...
2
votes
2answers
294 views

Divisibility in a recurrent sequence

Let $a_1=0$, $a_2=\alpha$, and $a_n=\lambda a_{n-1}+\mu a_{n-2}$ for $n\geq 3$. Are there positive integers $\alpha$, $\lambda$, $\mu$ such that $$a_{p^2} \equiv 0 \mod p $$ for every prime ...
2
votes
1answer
33 views

Simultaneous solutions of two inequalities involving prime numbers

Are there infinitely many solutions to the following inequalities (with $x\ne y$ and $x+y$ odd), $$x+y>p_{\pi(x)}+p_{\pi(y)+1}\tag{1}$$and $$x+y>p_{\pi(x)+1}+p_{\pi(y)}\tag{2}$$where ...
5
votes
1answer
57 views

Number of squarefree numbers and the Basel problem

Who discovered/proved that there are about $$ \frac{x}{\zeta(2)} $$ squarefree numbers up to $x$, or (roughly) when was this first known? Today I think this is considered 'obvious', but I don't know ...
0
votes
2answers
338 views

Upper bound number of distinct prime factors

I want to prove that if $\omega (n)$ is the number of distinct prime factors of $n$ for $n>2$ we have $\omega (n) \leq \frac{\ln n}{\ln \ln n} + O(\frac{\ln n}{(\ln \ln n)^2})$. How can I do this? ...
2
votes
1answer
54 views

Find all positive integers solutions such that $3^k$ divides $2^n-1$

How can I find all positive of $k$ and $n$ such that $$\frac {2^n-1}{3^k}$$ is an integer? I know that $$2^n-1\equiv 0\pmod 3$$ If $n=2p$ with $p$ integer , $$2^n-1\equiv 0\pmod 9$$ If $n=6p$, ...
20
votes
0answers
195 views

Can a number be equal to the sum of the squares of its prime divisors?

If $$n=p_1^{a_1}\cdots p_k^{a_k},$$ then define $$f(n):=p_1^2+\cdots+p_k^2$$ So, $f(n)$ is the sum of the squares of the prime divisors of $n$. For which natural numbers $n\ge 2$ do we have ...
14
votes
2answers
308 views

Is this olympiad-like question about remainders an open problem?

Suppose that we are given two positive integers $x$ and $y$ such that $$x \mod p \leqslant y \mod p$$ for each prime number $p$. (Here, $x \mod p,\; y \mod p$ stand for the least non-negative ...
0
votes
2answers
28 views

An inequality on the product of primes

Let $p_n$ denote the $n$-th prime ($p_1=2$) Let $\pi(n)$ be the numbers of primes less or equal to $n$. Prove that $$n^{\pi(2n)-\pi(n)}\leq \prod_{n+1\leq p_k\leq 2n}p_k\leq ...
2
votes
2answers
41 views

Why is it true for every prime $p>7$ that $p+1$ divides $\prod\limits_{[1,p]}\text{(the quadratic residues modulo $p+1$)}$?

Learning about the quadratic residues mod $n$ (link to Wikipedia), "$qr\ mod\ n$" for short, I made some tests focused on those $qr \in [1,n-1]$ (not including the quadratic residue $0$) and stumbled ...
4
votes
1answer
59 views

Least rational prime which is composite in $\mathbb{Z}[\alpha]$?

Sébastien Palcoux asked if there was some irrational algebraic $\alpha$ such that all rational primes are primes in $\mathbb{Z}[\alpha].$ MooS answered that there are no such $\alpha.$ This leads to a ...
1
vote
1answer
52 views

prime number and order problem

Does anyone can solve problem stated at Is $n = k \cdot p^2 + 1$ necessarily prime if $2^k \not\equiv 1 \pmod{n}$ and $2^{n-1} \equiv 1 \pmod{n}$? ? It should have the additional constraint, k < ...
2
votes
1answer
43 views

Is there a match between this modified prime pi function and the Log integral function?

Table T is defined as through the properties that accumulated row sums give prime numbers, while accumulated column sums give composite numbers. ...
0
votes
1answer
45 views

Prove that this algorithm generates the characteristic sequence of primes.

Prove that the characteristic function of primes is generated by this algorithm: $$T(1,1)=1$$ $$n=k: \;\; T(n,k)=1$$ $$\mod(n,k)=0: \;\; -\sum\limits_{i=1}^{n-1} T(n,k+i)$$ $$k=1: \;\; T(n,1)= ...
0
votes
1answer
28 views

Let $p > 2$ be prime. Show that there exist integers $a,b \geq 0 $ satisfying the congruence $a^2 + b^2 \equiv -1 $(mod $p$). [duplicate]

Let $p > 2$ be prime. Show that there exist integers $a,b \geq 0 $ satisfying the congruence $a^2 + b^2 \equiv -1 $(mod $p$). A few things that can be seen instantly: $ p \equiv 1$ mod $4$, ...
4
votes
1answer
96 views

What is the smallest prime of the form $2n^n+91$?

I wondered what the smallest prime of the form $2n^n+k$ is for some odd $k$. For $k<91$, there are small primes, but for $k=91$ , the smallest prime (if it exists) must be very large. What is the ...
1
vote
1answer
81 views

Prime number greater than n

Consider the follwing problem: Given $n$ (in binary) output a prime number $p \geq n$ (not necessarily the first prime number after $n$) Are there better techniques than the trivial one that scans ...
63
votes
4answers
4k views

$x$, $y$, $x+y$ and $x-y$ are prime numbers. What is their sum?

Here is the question: The $x$, $y$, $x−y$ and $x+y$ are all positive prime integers. What is the sum of all the four integers? Well, I just put some values and I got the answer. $x=5$, $y=2$, ...
16
votes
1answer
120 views

What is the smallest prime of the form $n^n+8$?

Is there a prime of the form $n^n+8$ , $n\in \mathbb N$ ? If yes, what is the smallest one ? It is clear, that $n$ must be odd and cannot be a multiple of $3$ (otherwise $n^n+8$ is of the form ...
44
votes
4answers
4k views

Eyebrow-raising pattern of number of primes between terms of the Fibonacci number sequence?

So, $$1,1,2,3,5,8,13,21...$$ Any connection to primes?...it appears not. However, in between the Fibonacci numbers are how much primes? Let's see: 1 and 1 ZERO 1 and 2 NADA 2 and 3 ZILCH 3 and 5 ZIP ...
3
votes
4answers
53 views

Prove that if $p$ is prime greater than $3$ ,then: $p^2+2015$ is multiple of $24$?

Prove that if $ p $ is prime number $(p >3)$, then the number $p^2+2015$ is multiple of $24 $? Thank you for any help
4
votes
1answer
54 views

An inequality on the series of powers of reciprocals of the primes

Let $p_n$ denote the $n$-th prime $(p_1=2)$ Let $s>1$ Prove that $\displaystyle-1+\ln(\frac{s}{s-1})\leq\sum_{k=1}^\infty\frac{1}{p_k^s}\leq\ln(\frac{s}{s-1})$ Using the classical ...
0
votes
0answers
72 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 ?
14
votes
1answer
855 views

Finding smallest and largest prime factor of $\frac{200!}{180!}$

I originally started off by listing all the primes: $p<200$ then trying to calculate the prime factorisation of each (which I realise is a silly thing to do) I believe there must be a simpler way ...
2
votes
1answer
26 views

Is this Bertrand's postulate-related statement valid?

Bertrand's postulate says: For every $n>1$ there is always at least one prime $p$ such that $n<p<2n$. Is the following statement: For every $n>3$ there is always at least one ...
4
votes
0answers
41 views

Number of lucky primes

The "lucky numbers" can be constructed with this sieve. The red ones are the lucky numbers. As you can see, some are prime. Is the number of lucky primes infinite? Edit: Apparently this is an open ...
3
votes
3answers
56 views

Is there a counterexample? $\forall\ p \gt 3 \in \Bbb P, (number\ of\ Quadratic\ Residues\ mod\ kp)=p\ when\ k\in\{2,3\}$

I have started to learn about the properties of the quadratic residues modulo n (link) and reviewing the list of quadratic residues modulo $n$ $\in [1,n-1]$ I found the following possible property: ...