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

3
votes
2answers
316 views

Calculating prime numbers

I have a program which determines if a number is prime or not. The basic algorithm simply checks for the number being divisible by 1 and itself. My question is, is there an upper limit to checking ...
3
votes
2answers
246 views

Are there infinitely many primes and non primes of the form $10^n+1$?

Prove that there are infinitely many primes and non-primes in the numbers $10^n+1$, where $n$ is a natural number. So numbers are 101, 1001, 10001 etc.
2
votes
3answers
313 views

RSA: Encrypting values bigger than the module

Good morning! This may be a stupid one, but still, I couldn't google the answer, so please consider answering it in 5 seconds and gaining a piece of rep :-) I'm not doing well with mathematics, and ...
11
votes
3answers
582 views

How to prove Chebyshev's result: $\sum_{p\leq n} \frac{\log p}{p} \sim\log n $ as $n\to\infty$?

I saw reference to this result of Chebyshev's: $$\sum_{p\leq n} \frac{\log p}{p} \sim \log n \text{ as }n \to \infty,$$ and its relation to the Prime Number Theorem. I'm looking into an ...
3
votes
3answers
192 views

Modular multiplication with machine word limitations

Imagine I have 64-bit machine and the widest integer available is 64-bit signed long. I cannot use BigInteger or similar libraries for performance reasons, and all calculations I get would me modulo ...
1
vote
1answer
207 views

Prime numbers which solve $2^s=1\pmod p$

Here we define those primes $p$ for which $\operatorname{ord}_p(2)=s$, where $s$ is the minimum of the set $S$ of all divisors $d\mid p-1$ such that $2^d-1\geq p$. For example: for $p=7$, $s=3$, ...
0
votes
0answers
97 views

If $p$ is prime > 3,what does $m$ equal to within this expression $\sum_{i=1}^{p-1}1/i = \dfrac{m}{n}$ [duplicate]

Possible Duplicate: General formula for $\sum_1^{p-1} \frac{1}{x}$, where $p$ is an odd prime If $p$ is prime > 3,what does $m$ equal to $\sum_{i=1}^{p-1}\dfrac{1}{i} = \dfrac{m}{n}$ I need to ...
122
votes
6answers
22k views

Deleting any digit yields a prime… is there a name for this?

My son likes his grilled cheese sandwich cut into various numbers, the number depends on his mood. His mother won't indulge his requests, but I often will. Here is the day he wanted 100: But ...
4
votes
0answers
272 views

Prime zeta definition, multiplication by zero

Wikipedia has a page about the prime zeta function which is defined as follows: $$P(s)=\sum_{p\;\text{prime}} \frac1{p^s}$$ I entered this additional definition: Define a sequence: ...
3
votes
2answers
285 views

$n = 2^k + 1$ is a prime iff $3^{\frac{n-1}{2}} \equiv -1 \pmod n$

Let $k \geq 2$ be a positive integer and let $n=2^k+1$. How can I prove that $n$ is a prime number if and only if $$3^{\frac{n-1}{2}} \equiv -1 \pmod n.$$ Fixed.
3
votes
2answers
227 views

All primes $p,q,r$ such that $(p-q)^2+1=r$

How can one find all prime numbers $p,q,$ and $r$ such that $$(p-q)^2+1=r\ ?$$
5
votes
2answers
243 views

For which prime $p$ are the additive groups $\mathbb{F}_p$ and $\mathbb{F}_p^2$ $\mathbb{Z}[i]$-modules?

Homework for my algebra class. Chapter 14, Exercise 7.8 in Artin's Algebra, Second Edition: Let $F = \mathbb{F}_p$. For which prime integers $p$ does the additive group $F^1$ have a structure ...
2
votes
2answers
861 views

Congruence modulo prime power

In the book "A Classical Introduction to Modern Number Theory", I saw the following theorem (p. 43): If $p\neq 2$, and $p\nmid a$ then $p^{l-1}$ is the order of $(1+ap)$ mod $p^l.$ i.e. ...
5
votes
2answers
705 views

Euler's phi function and distinct primes

It is true that $\phi(p) = (p-1)$ only if p is a prime. I had also proven (I am not sure if this is a trivial fact or not) that $\phi(pq) = (p-1)(q-1)$ only if p and q are distinct primes. However, I ...
41
votes
2answers
4k views

The square roots of different primes are linearly independent over the field of rationals

I need to find a way of proving that the square roots of a finite set of different primes are linearly independent over the field of rationals. I've tried to solve the problem using ...
6
votes
2answers
1k views

Proof that there are infinitely many primes of the form $4m+3$

I am reading a proof of there are infinitely many primes of the form $4m+3$, but have trouble understanding it. The proof goes like this: Assume there are finitely many primes, and take $p_k$ to be ...
16
votes
4answers
3k views

Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?

This question relates to a discussion on another message board. Euclid's proof of the infinitude of primes is an indirect proof (a.k.a. proof by contradiction, reductio ad absurdum, modus tollens). My ...
2
votes
1answer
55 views

Is there a generalisation of the distribution ratio

From the theory of numbers we have the Proposition: If $\mathfrak{a}$ and $\mathfrak{b}$ are mutually prime, then the density of primes congruent to $\mathfrak{b}$ modulo $\mathfrak{a}$ in ...
2
votes
1answer
201 views

How fast can we find primes (number of computations needed+time for the computation too)

So, I know we can get a bound on how long it will take to find a large prime. For example, using the fact that between $N$ and $2N$ there must be a prime. And the fact that all numbers between are ...
9
votes
1answer
307 views

Sum of cosines of primes

Let $p_n$ be the nth prime number, $p_1=2,p_2=3,p_3=5,\ldots$ How to prove this series converges/diverges? $$\sum_{n=1}^\infty \cos{p_n}$$
1
vote
3answers
258 views

Prove the product of a sum of powers of primes diverges

I need to prove that this is divergent: $$\prod_{\stackrel{p\leq N}{p\text{ prime}}}\left(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots + \frac{1}{p^k} + \cdots\right),$$ where the expression inside of the ...
7
votes
3answers
207 views

Combinatorics question: Show divisibility

Let $a\geq2$, $b\geq2$ be two prime numbers and k be a natural number with $k\leq min(a,b)$. How can one show that $z := \binom{a+b}{k} - \binom{a}{k} - \binom{b}{k}$ is divisible by the product ...
10
votes
3answers
506 views

prove that $\lim_{x\to\infty} \pi(x)/x=0$

I think I might have asked this question before, but I can't find it on the site, so I sincerely apologize if I am making a duplicate. But anyway, I have been working on this proof for several weeks ...
12
votes
2answers
1k views

Every even integer can be expressed as the difference of two primes?

Every even integer can be expressed as the difference of two primes? If so, is there any elementary proof?
38
votes
1answer
1k views

Sums of prime powers

You are given positive integers N, m, and k. Is there a way to check if $$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\equiv0\pmod m$$ faster than computing the (modular) sum? For concreteness, you ...
4
votes
1answer
105 views

Partitioning polynomials in $\mathbb{Z}[x,y]$ by the primes they represent

Suppose you have a set $S\subset\mathbb{Z}[x,y].$ How can one efficiently partition the polynomials into sets such that the primes represented by the polynomials in any given set are identical? For ...
5
votes
2answers
680 views

A first order sentence such that the finite Spectrum of that sentence is the prime numbers

The finite spectrum of a theory $T$ is the set of natural numbers such that there exists a model of that size. That is $Fs(T):= \{n \in \mathbb{N} | \exists \mathcal{M}\models T : |\mathcal{M}| =n\}$ ...
3
votes
3answers
406 views

Is it true that all senary numbers ending in 1 and 5 are primes?

I was reading the Wikipedia article on senary numbers (base 6), which states that: all primes, when expressed in base-six, other than 2 and 3 have 1 or 5 as the final digit Unless I am ...
5
votes
2answers
599 views

distance between consecutive primes (related to Polignac's conjecture)

Is there an elementary(or not) proof that there are at least two consecutive primes which have difference $2n$ for every natural number $n$? i remind that Polignac's conjecture states that there ...
6
votes
2answers
368 views

Relative density of primes under extension

Let $\mathbb{P}_{\mathbb{C}}$ be the set of Gaussian primes and $\mathbb{P}_{\mathbb{N}}$ the set of primes in $\mathbb{N}$. Let $\pi_{\mathbf{C}}(\sqrt{n})$ be the number of Gaussian primes with ...
1
vote
2answers
104 views

Estimating the Primarithm

Let's define the primarithm function, $pog : \mathbb{N} \rightarrow \mathbb{N}$, where $pog(n)$ is the largest number of distinct primes that can divide a natural number $k$, $k \leq n$. Does this ...
4
votes
1answer
1k views

Prime-power decomposition of a square

I'm trying to learn number theory on my own, and here's a proof I'm not quite sure I got right. It feels too simple(?), I'm thinking maybe I'm missing something. So the question is: Prove that if ...
4
votes
1answer
270 views

Prime divisors of $n-1$, prove $n$ is prime

Can anybody help me out with this number theory question? My question is as follows: If $n$ is a positive integer and if an integer $x$ exists such that $x^{n-1}\equiv 1 \pmod n$ and ...
5
votes
1answer
310 views

Square-free zeta function zeros

It is a well known fact that the geometric series $$1+x+x^2+x^3+\ldots$$ has the following form $$\frac{1}{1-x}$$ Another possible representation is $$\prod_{k=0}^{\infty}\left(1+x^{2^{k}}\right)$$ ...
1
vote
1answer
162 views

Proof of Primality Testing

I am learning some Cryptography and I came across this exercise where I have to make the following proof (translated from German, so I hope it is accurate). Proof the following assertion: Let $n ...
4
votes
2answers
196 views

$h+k=p-1$, $p$ prime. Prove $h!k! + (-1)^h \equiv 0 \pmod{p}$?

Suppose that $p$ is a prime. Suppose further that $h$ and $k$ are non-negative integers such that $h + k = p − 1$. I want to prove that $h!k! + (−1)^h \equiv 0 \pmod{p}$ My first thought is that by ...
1
vote
1answer
907 views

Prime factorization of square numbers

Let n be a natural number with unique prime factorization $p^m$... $q^k$ . Show that n can be written as a square if and only if all (m, ...k) are even
4
votes
3answers
627 views

What set of $10$-digit numbers with $k$ prime factors has largest cardinality?

Suppose $s_{1}$ are the numbers with 10-digits that have $1$ prime factor. Suppose $s_{2}$ are the numbers with 10-digits that have $2$ prime factors. Suppose $s_{n}$ are the numbers with 10-digits ...
4
votes
1answer
124 views

Prove that If $f_n$ where $n>3$ is prime, then $n$ is prime for a Fibonacci series where $f_1$=$f_2$=1

This problem came up in my conversation with a friend—not sure how basic it is, but it seems quite interesting: Prove that if $f_n$ where $n>3$ is prime, then $n$ is prime for a Fibonacci sequence ...
21
votes
3answers
406 views

Computing the product of p/(p - 2) over the odd primes

I'd like to calculate, or find a reasonable estimate for, the Mertens-like product $$\prod_{2<p\le n}\frac{p}{p-2}=\left(\prod_{2<p\le n}1-\frac{2}{p}\right)^{-1}$$ Also, how does this behave ...
12
votes
6answers
1k views

Does the formula $\sqrt{ 1 + 24n }$ always yield prime?

I did some experiments, using C++, investigating the values of $\sqrt{1+24n}$. ...
3
votes
3answers
279 views

bound of the number of the primes on an interval of length n

I made this observation and it seems reasonable to me to ask :if $n$ is a natural number then the number of the primes less than or equal to $n$ is denoted by $π(n)$ . is that true that in any ...
1
vote
2answers
2k views

Help in understanding the proof of Mersenne Prime

Problem: $$\text{ If } 2^{n} - 1 \text{ is prime then n is prime}$$ Proof 1: $$\text{If } n = kl \text{ with } 2 \leq k, l < n \text{ then } (2^{k} - 1)|(2^{n} - 1). \text{ Hence if } 2^{n} - 1 ...
8
votes
2answers
3k views

Help understand the proof of infinitely many primes of the form $4n+3$

This is the proof from the book: Theorem. There are infinitely many primes of the form $4n+3$. Lemma. If $a$ and $b$ are integers, both of the form $4n + 1$, then the product $ab$ is also in ...
2
votes
3answers
828 views

Show that every $n$ can be written uniquely in the form $n = ab$, with $a$ square-free and $b$ a perfect square

I need to show that every positive integer $n$ can be written uniquely in the form $n = ab$, where $a$ is square-free and $b$ is a square. Then I need to show that $b$ is then the largest square ...
11
votes
5answers
2k views

Prove a number is composite

How can I prove that $$n^4 + 4$$ is composite for all $n > 5$? This problem looked very simple, but I took 6 hours and ended up with nothing :(. I broke it into cases base on quotient remainder ...
-1
votes
3answers
540 views

Prime number rule

I was requesting somebody to help me discuss how the prime number rule helps to solve easily the sudoku game in just a few minutes and an example showing the relevant steps on how the rule is used
4
votes
2answers
593 views

Prove that an odd integer $n>1$ is prime if and only if it is not expressible as a sum of three or more consecutive integers.

Prove that an odd integer $n>1$ is prime if and only if it is not expressible as a sum of three or more consecutive integers. I can see how this works with various examples of the sum of three or ...
5
votes
2answers
389 views

No prime number between number and square of number

Find the values of $x \in \mathbb{Z}$ such that there is no prime number between $x$ and $x^2$. Is there any such number?
2
votes
2answers
1k views

Prime powers that divide a factorial [duplicate]

Possible Duplicate: How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes? If we have some prime $p$ and a natural number $k$, is there a formula ...