Tagged Questions

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

8
votes
2answers
179 views

On the difference between consecutive primes

Let $(p_n)$ be the sequence of prime numbers and $g_n = p_{n+1} - p_n$ Question: Is it known that $g_n \le n$? Remark: it's known that $g_n < p_n^{\theta}$ with $\theta = 0.525$ for $n$ ...
3
votes
2answers
22 views

Math for Computer Science

I have a couple of questions on the material in "Mathematics for Computer Science" by Eric Lehman and Tom Leighton. Q1. This is a theorem in the book: Theorem 24. Let $p$ be a prime. If $p|a_1a_2 ...
2
votes
0answers
62 views

Conjecture on sum of powers

Let $n$ be an odd number, $x,y$ integers and $p$ a prime number. Now, suppose that $p\ne n$ and $$ p|\frac{x^n+y^n}{x+y} $$ Then, I have been observed that $p \equiv 1 \pmod{n}$. This is, all of the ...
0
votes
1answer
35 views

Find a real $β$ such that $(β^{2^{p-1}}+1)/(β^{2^{p-2}}(2^{p}-1))$ is an integer [closed]

Let $p$ a prime number. Find a real $β$ such that $(β^{2^{p-1}}+1)/(β^{2^{p-2}}(2^{p}-1))$ is an integer.
1
vote
2answers
51 views

Prime numbers and $\sqrt{10301}$

On my exam recently, we had the following question: Use the prime number theorem to estimate the number of primes less than $\sqrt{10301}$, and hence, give a concise argument whether 10301 is prime ...
1
vote
1answer
32 views

Something similar to Euler's theorem

If $p$, $q$ are not equal primes. $n=pq$, $\varphi(n) = (p − 1)(q − 1)$, $d = \gcd(p − 1, q − 1)$. Is it true that for any $a$ such that $\gcd(a, n) = 1$ holds $a^{\frac{\varphi(n)}{d}} \equiv 1 ...
1
vote
2answers
82 views

Finding prime solutions to $100q+80 = p^3 + q^2$

Finding prime solutions to $100q+80 = p^3 + q^2$ Does them being prime imply some patterns on division modulo 3 or some other integer? How is this done?
0
votes
1answer
52 views

Search for very large prime (greater than $2^{57885161} − 1$) between Crystal Numbers

Denote $p[i]$ as the $i$th prime. In my opinion, the following is true: Prime Gap Axiom There are always distinct prime factors for $\{p[i],p[i]+1,p[i]+2, \dots , p[i+1]\}$. Question 1 How to ...
2
votes
3answers
71 views

Finding all natural $n$ such that $2^n+2^{2n} +2^{3n}$ has only $2$ prime factors.

Find all natural $n$ such that $2^n+2^{2n} +2^{3n}$ has only $2$ prime factors. I've tried checking the first 6-7 $n$'s on wolframalpha, but I don't see any patterns for even nor odd $n$'s. At first ...
3
votes
0answers
68 views

How prime numbers are related to special functions?

We know that the Riemann zeta function is defined as $$\zeta(s)=\sum_{n=1}^\infty\frac{1}{n^s},$$ for all $\Re(s)>1$. Because of Euler product formula we also know that $$\zeta(s) = ...
2
votes
1answer
46 views

Is there a way to relate prime numbers and the fourier transform

According to what I know about Fourier transforms, any continuous periodic signal can be represented as a combination of sine and cosine functions. To me, this looks analogous to the "Fundamental ...
2
votes
1answer
23 views

distribution of gaussian primes

here is a naive question that so far I don't have already found somewhere else. In the following, I consider the norm on gaussian integers with $N(a+ib)=a^2+b^2$. Consider prime gaussian integers ...
4
votes
2answers
48 views

$(n+1)^{\textrm{st}}$ prime less than $2^{2^n}$

Using elementary means, show that the $(n+1)^{\textrm{st}}$ prime is less than $2^{2^n}$ please do not use fancier stuff like the prime number theorem or beyond. using this how can you show that ...
0
votes
1answer
5 views

Discrete algebra and exponents (See body text)

Let $a,b\in\mathbb{Z}^+$. If $a \equiv b\bmod 49$, and $\gcd(a,49) = 1$. How can I find any positive integer $n > 1$, so that $b^n\equiv a\bmod 49$? I'm completely stumped by this. I've been ...
2
votes
1answer
25 views

Calculating the power of prime in factorial by changing base

The greatest power $k$ of a prime $p$ in the prime factorization of $n!$ is equal to $\frac1{p-1}(n-s(n)_p)$, where $s(n)_p$ is the sum of digits of $n$ when represented in base $p$. How to ...
3
votes
1answer
71 views

Convergence of infinite product of prime reciprocals?

Where pn is the nth prime number, does the infinite product $$\prod_{n=1}^{\infty}\left(1-\frac{1}{p_n}\right)$$ converge to a nonzero value? (Any help would be much appreciated!)
0
votes
1answer
32 views

Decryption of a RSA encrypted message is not working.

Using RSA with e=13 (encrypting power), d=17 (decrypting power) & n=33 (RSA modulus) I noticed that once I decrypted the encrypted message it would be different then the original message. Why is ...
0
votes
0answers
25 views

The representations of numbers by decimals

I'm looking for books that talk about the representation of the integers by decimals, more specifically for prime numbers. I can't found anything yet, I read something in "AN INTRODUCTION TO THE ...
1
vote
2answers
28 views

Can we find an integer $m$ such that: $2^{2p-2}-2^{p}+3=m²$

Let $p$ a prime number. Can we find an integer $m$ such that: $$2^{2p-2}-2^{p}+3=m²$$
1
vote
3answers
48 views

What makes the Mersenne primes formula more special than any of these formulas?

Mersenne Primes Formula $2^n-1$ gives false results just like any of those ones: $3^n-2, 4^n-3, P_1\cdot P_2+P_1+P_2$, or $5^n-4$ and so on.. I think that each of those formulas(including ...
0
votes
2answers
86 views

What is the number of digits of this number: $2^{333111160}$? [duplicate]

My question is: What is the number of digits of this number? : $$2^{333111160}$$
1
vote
1answer
39 views

to count the intervals

A finite set of two or more consecutive natural numbers is called a "co-prime interval" if there is no number in it that is co-prime to all other numbers in the set. Given a range [A, B], I would ...
4
votes
2answers
42 views

Can we find $n$ such that $p|2^n-1$ for a given prime $p.$

For a given prime $p$ can we find a positive integer $n$ such that $p$ is a divisor of $2^n-1.$ I know, choosing a large $n$ we can do this. But is there any proof for this? I have no idea for start a ...
4
votes
2answers
82 views

Does there exist an $a_0$ such that the sequence $a_{n+1} = 2a_n + 1$ is prime for all $n \ge 0$?

I believe I see that $a_n = 2^n(a_0+1) - 1$ but am somewhat uncertain where to proceed afterwards. I am a complete beginner at number theory and would appreciate it if someone could point me in the ...
1
vote
1answer
57 views

Question about any 2 distinct primes and the difference between their multiples

I've been thinking about the following situation. Let $p$,$q$ be two distinct primes. Let $a,b \le pq$ be any two numbers such that $a \ge b$ where $p$ divides $a$ or $b$ and $q$ divides the other. ...
2
votes
2answers
69 views

Proving that if $p$ is a prime number then $gcd (p, (p-1)!) =1$

I am just making sure whether this is a valid proof: Since $p$ is a prime number, then $p$ is only divisible by $1$ or $p$ Suppose we want to take the $gcd (p,a)$ with a, an arbitrary ...
0
votes
4answers
68 views

Is it true that $2^{p}-1$ is a prime number?

Let $p$ be an odd prime such that $$p \equiv 1 \pmod{4}$$ and $p$ and $p-2$ form a twin prime pair. My question: Is it true that $2^{p}-1$ is a prime number?
1
vote
2answers
24 views

If $p,q$ are prime, $q$ odd $p \not\equiv 1 \pmod q$, is there an integer $x$ such that $p\mid 1+x+\ldots+x^{q-1}$

Suppose $p,q$ are two distinct prime numbers, $q \geq 3$ and $p \not\equiv 1 \pmod q$. Then I have the following problem: Prove that there is no integer $x \in \mathbb{Z}$ such that ...
0
votes
1answer
26 views

About a recurrence equation of prime numbers

Let $p$ be a prime. Consider the recurrence equation $$s_{n}=(s_{n-1}²-2)(mod(2^{p}-1))$$ where $s₀=4$ My question is: Can we write this recurrence as follow? $$s_{n}=(2^{p}-1)q+(s_{n-1}²-2)$$ ...
1
vote
2answers
59 views

Can this be solve using modular arithmetic? $k$ is prime $\Rightarrow$ $8k+1$ is prime

Is the following statement true or false? $\forall k \in \mathbb{N}, k$ is prime $\Rightarrow$ $8k+1$ is prime The answer is that the statement is false because if $k=7$, then $k$ is prime but ...
0
votes
0answers
21 views

Primality of Stirling numbers of second kind

Apart from the Mersenne primes $M_p=2^p-1=S(p+1,2)$, and the four primes $S(n,4)$ where $n$ is given in http://oeis.org/A100958, are there other Stirling numbers of the second kind $S(n,k)$ which are ...
0
votes
2answers
53 views

Which of the following is true?

Let $\hspace{0.2cm}$$p,q,r$$\hspace{0.2cm}$ be prime numbers greater than 100,then which of the following is true? $3|p^2+q^2+r^2$ $q|p^5$ There exists integers $x,y$ such that ...
3
votes
1answer
30 views

Can we have $\sum_{n\leq [x]}e^{-\sqrt{\frac{\log x}{r}}}\ll \frac{x}{e^{c \sqrt{\log x}}}$ for some constant $c>0$, where $x>1.$

Let positive interger $n$ is square-free, that is $n=p_1p_2\cdots p_r$ some $r$. Can we have $$\sum_{n\leq [x]}e^{-\sqrt{\frac{\log x}{r}}}\ll \frac{x}{e^{c \sqrt{\log x}}}$$ for some constant ...
0
votes
1answer
26 views

Primes Involved in GCD

If p is a prime number, prove that gcd(p, (p-1)!) = 1 So, I've tried using the fact that 1 = px + (p-1)!y, where x,y are integers, but from there I'm stuck and don't really know how to work with the ...
2
votes
1answer
56 views

Prove that $p \ge 5$ is prime, then the remainder of $p$ upon division by $6$ is $1$ or $5$.

An example in my textbook, but I'm not quite sure how to set this one up, because of the $p \ge 5$ part. How do I start it off?
2
votes
1answer
34 views

If $p$ is prime and $\sigma(p^k) = n$, then $p\mid (n-1)$

If $p$ is prime and $\sigma(p^k) = n$, then $p\mid (n-1)$. proof: Suppose $\sigma(p^k) = [p^{k+1} -1]/(p-1) = n$. Then $n-1 = [p^{k+1} -1]/(p-1) - 1= [p^{k+1} -1 - (p-1)] /(p-1) = [p^{k+1} - ...
1
vote
1answer
44 views

Divisibility and Primes

Suppose that $p,q,r$ are prime numbers and $p$ is odd. If $p\,|\,(2q+r)$ and $p\,|\,(2q-r)$, prove that $q=r$. So I'm trying to use the definition of greatest common divisor to come up with two ...
0
votes
3answers
34 views

Canonical decompositions and product of primes

Let $S$ be the set of natural numbers $n$ that have exactly $9$ positive divisors. Describe all possible canonical decompositions (as products of primes) of elements of $S$.
0
votes
0answers
59 views

Prime Reflections

How would you describe the following pattern?: For each primorial from 30 onward, there exists a pattern in the arrangement of the prime factors of the composite numbers which I call "the mirror ...
0
votes
1answer
42 views

A function that maps a value to a large prime

I'd like to ask whether there is any function that maps a value to a large prime in deterministic way, so this function always maps the same value to the same large prime. The large prime here ...
1
vote
1answer
62 views

Sum of inverse prime numbers

How can the following equation be proven? $\sum\limits_{p \le n; p \in P} \frac{\ln p}{p} \sim \ln(n) + O(1).$ I just wanna understand this sum Sum of reciprocal prime numbers
1
vote
1answer
40 views

One Half of a Primorial

Is there a name for a half primorial? How should a half primorial be notated? The first three primorials are 2,6, and 30. The first three half primorials are 1,3, and 15. I have found that the half ...
3
votes
0answers
24 views

Given $n$, find $a,b$ such that $a+b=n$ and $\Omega(a)+\Omega(b)$ is maximized

Given a number $n$, find $a,b$ such that: $a,b$ non-negative integers $a+b=n$ $\Omega(a)+\Omega(b)$ is maximized $\Omega(n)$ counts the number of prime factors of n (with multiplicity). ...
2
votes
2answers
79 views

Can Andrica's conjecture be proven by proving a tighter upper bound for prime gaps?

I checked some differences between square roots of various natural numbers and I am wondering what is required to prove Andrica's conjecture. Would a tighter upper bound for the prime gap above $n$ be ...
0
votes
0answers
53 views

Proof for divisibility on a prime test: (p-1)!/(n!(p-n)!)

$p$ is a prime only if $\forall n \in\{ 2, 3, .. ,\lfloor \frac{p}{2}-1\rfloor, \lfloor \frac{p}{2}\rfloor \}$: $\dfrac{(p-1)!}{n!(p-n)!}\in \mathbb N$ The remainders and n's that don't divide when ...
0
votes
2answers
49 views

How do we identify the $n$th prime?

The 1st prime is 2. The 2nd prime is 3. The 3rd prime is 5. So if $\pi(x)=1$, the prime is 2. If $\pi(x)=2$, the primes are 2 and 3, but how do we identify them? If $\pi(x)=3$, I know that there are ...
2
votes
0answers
23 views

Significance of formulas similar to summation formula

We all know formula $n(n+1)/2$ for adding up the numbers from $1$ to $n$. But I would like to know if there is any significance and use of formulas of type $n(n^{p-1}+p-1)/p$, where $p$ is a prime. ...
1
vote
0answers
31 views

The Existence of “Simple” Prime Generating Functions

Obviously, we do not know an explicit and easily manipulable formula for finding every prime - that is, a function $f(n)$ which yields the $n^{th}$ prime. I've seen plenty of formulas that "cheat" in ...
1
vote
0answers
10 views

Does a random binary sequence almost always have a finite number of prime prefixes?

Does a random binary sequence almost always have a finite number of prime prefixes? Specifically, let $x = \sum_{1 \le i}{2^{-i} \cdot x_i}$ with $x_i \in \{0,1\}$ be a random real in $[0,1)$, $X_i = ...
3
votes
2answers
113 views

The Conjecture That There Is Always a Prime Between $n$ and $n+C\log^2n$

Let $n$ be 113. Use $n+C\log^2n$ to find the next consecutive prime or at least approximately how far away it is. Will you show me how to work this out step by step to show me how to use this formula? ...