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
19 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 ...
1
vote
2answers
30 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$ ...
2
votes
2answers
55 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
1answer
39 views

What is the asymptotic behavior of the function counting the number of (not necessarily distinct) prime divisors?

From http://en.wikipedia.org/wiki/Arithmetic_function#.CE.A9.28n.29.2C_.CF.89.28n.29.2C_.CE.BDp.28n.29_.E2.80.93_prime_power_decomposition Ω(n), ω(n), νp(n) – prime power decomposition The ...
0
votes
1answer
27 views

Will the Product of a Set of Primes above 1 ever be Equal to The Product of a Different Set of Primes above 1

Given two sets a and b. When a and b only contain primes ...
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
34 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 ...
0
votes
0answers
16 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 ...
4
votes
1answer
38 views

Solving a Diophantine equation with LTE

Show that only positive integer value of $a$ for which $$4(a^n+1)$$ is a perfect cube for all positive integers $n$, is $1$. Rewriting the equation we obtain: $$4(a^n+1)=k^3$$ It is obvious that $k$ ...
2
votes
1answer
27 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 ...
1
vote
2answers
40 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 ...
1
vote
1answer
77 views

Confusion on Mersenne Numbers

One fundamental theorem on Mersenne Numbers states: If $q$ is a prime of the form $8k+7, q|M_{(q-1)/2}=2^{(q-1)/2}-1$. Let $q=7+768z$, So ...
0
votes
1answer
39 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
1answer
58 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$, ...
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 ...
-2
votes
2answers
53 views

Why modulo prime prefered over modulo composite?

In encryption process(aes encryption)and also in Galois field, a prime number is always used to perform the modulo operation. So I wanted to know the reason for using only prime numbers for modulo ...
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 ...
6
votes
0answers
204 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 ...
26
votes
2answers
367 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 ...
2
votes
2answers
43 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 ...
1
vote
1answer
54 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 < ...
0
votes
1answer
29 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$, ...
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)= ...
4
votes
1answer
98 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 ...
3
votes
4answers
55 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
16
votes
1answer
125 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 ...
0
votes
2answers
29 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 ...
0
votes
0answers
73 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 ?
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
43 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 ...
4
votes
1answer
55 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 ...
3
votes
0answers
20 views

Special $\omega(n)$-sequence

Let $k$ be a natural number, $\omega(n)$ the number of distinct prime factors of $n$. The object is to find a number $n$ with $\omega(n+j)=j+1$ for each $j$ with $0\le j\le k-1$. In other words, a ...
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: ...
0
votes
2answers
48 views

Pattern for generating primes and semiprimes?

First, is there a formula that can generate semiprimes in polynomial time? Also, I found this interesting pattern: $$3x+1, 3x+2$$ Inputting increasing natural x spits out $$7, 11, 13, 17, 19, 23, 25, ...
0
votes
1answer
90 views

Brain-explosion pattern of primes and the number 30? [closed]

Prime numbers. Elusive little snips. They give you a warm trail with a dead end. Here's another one of those pattern 'trails': $$30$$ Normal number? How about 'expanding' outward? $$29, 30, 31$$ Yea, ...
45
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 ...
5
votes
2answers
99 views

Inifinitely many primes $p\equiv -1 \mod12$

I haven't been able to prove this statement from my Elementary Number course: There are infinitely many primes $p$ such that $p\equiv -1 \mod12$. From here I know that there exists a "Eulcidean ...
0
votes
0answers
60 views

Is $74*2^n - 1$ prime for some $n$?

Hello I could not find google´s answer for this one, and my computer became ill when reached $n = 1300$ (I hope did n´t some mistake), but some clever people said to me yes, there is $n$ where this ...
5
votes
1answer
103 views

theorem relating mersenne numbers?

For $(x2^9)^2=2^q-1+y^2q^2$,where $q$ is prime, is it possible to show that there exists only an unique solution for the pair $\{x,y\}$?
4
votes
1answer
42 views

Number of primes between $2k$ and $(\sqrt{k}-1)^2$.

I would like to prove the following. Let $\pi$ denote the prime counting function. Then for $k\geq 81$ we have $$ \pi(2k)-\pi\left(\left\lfloor(\sqrt{k}-1)^2\right\rfloor\right)\geq 6. $$ What I ...
1
vote
3answers
66 views

Find $y$ satisfying $17y = 1 \mod (130)$

Let $x=17$ $n=130$. Find $y; (1\leq y \leq n-1)$ that satisfies :$$xy=1 \pmod n$$ Now I'm not sure if I should use one of Euler's theorem's for prime numbers? Can anyone help? Or try something with ...
6
votes
2answers
426 views

Number theory, prime numbers

prove that for all prime numbers $p>2000$ the sum $$1+2^{2000}+3^{2000}+...+(p-1)^{2000}$$ is divisible by $p$ I tried this with primes smaller then $2000$, but I can't find a general rule.
4
votes
0answers
111 views

Test about prime gaps

I did the following test: For every prime, take the prime gap distance $dp$ to the previous prime and the next prime $dn$, then calculate $a=(pp\ mod\ dp)$ and $b=(np\ mod\ dn)$. If $a$ or $b$ ...
4
votes
1answer
51 views

Sum of reciprocals of primes diverges

I can show that $$\log(\zeta (s)) = \sum _{p\in\Bbb P} \frac{1}{p} + R(s)$$where $$R(s) = \sum _{m\geq 2} \sum_{p\in\Bbb P} \frac{1}{m} \frac{1}{p^{ms}}$$ where $\Bbb P$ is the set of all primes, ...
0
votes
1answer
39 views

Find the lowest value of $x$ so that $x \in (A \setminus B)$

Let $A$ and $B$ be two sets for which the following applies: $A = \{x: \text{GCD(}x,12) = 1\}$ $B = \{x: x\ \text{is a prime}\}$ Find the lowest value of $x$ so that $x \in (A \setminus B)$. $x \in ...
2
votes
1answer
69 views

Can the expression $6^{2n} - 25$ be a prime for all $n \geq 2$?

Can the expression $6^{2n} - 25$ be a prime for any $n \geq 2$? My attempt to solve the problem: No, it cannot. $6^{2n} - 25 = (6^{n})^{2} - 25 = (6^{n})^{2} - 5^{2} = (6^{n} + 5)(6^{n} - 5)$ And ...
2
votes
1answer
37 views

for which values of the pair of integers $(n,k)$ is $p(n,k) =1+\frac{2^{k}-1}n$ is prime?

let $p(n,k)= 1+\frac{2^{k}-1}{n}$ for a positive integer $n,k$ -for which values of the pair of integers $(n,k)$ : $p(n,k)$ is prime ? Any help is very welcom .Thank you
0
votes
2answers
106 views

How to find the greatest prime number that is smaller than $x$? [duplicate]

I want to find the greatest prime number that is smaller than $x$, where $ x \in N$. I wonder that is there any formula or algorithm to find a prime ?
2
votes
1answer
47 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. ...
1
vote
0answers
63 views

Is the Ulam Spiral just a coincidence?

I was messing around with the Ulam spiral because I was a little skeptical on it having any actual relevance. I noticed that if you lay out the spiral and then circle all the even numbers, it displays ...