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

1
vote
0answers
239 views

Anti-prime sequence

I have permutation from $x$ to $y$. And how to make sequence which $d$ summed numbers from this sequence ISN'T a prime number. if we have sequence $x_1,x_2,x_3,x_4,x_5 \dots y$ than $d$ means : ...
3
votes
4answers
234 views

Can a number have a prime factor that isn't a part of the number's prime factorization?

Is it possible to have a number, $x$, divisible by some prime, such that that prime does not appear in the unique prime factorization of $x$?
3
votes
1answer
130 views

Find a finite extension of $\mathbb{Q}$ in which all primes split

Dear all, I would be grateful if someone could provide a solution to the following problem (using decomposition and inertia groups): Find a finite extension of $\mathbb{Q}$ in which all primes split. ...
7
votes
2answers
233 views

Given $2$ randomly chosen integers $x,y$ what is $P(k=gcd(x,y))$?

Given $2$ randomly chosen integers $x,y$ what is the probability that a integer $k$ is the greatest common divisor of $x$ and $y$? I know that the probability of $x,y$ being coprime is ...
2
votes
2answers
136 views

Calculations with liars and sums of prime factors

Suppose you are given a number $n$ and told that the sum of its prime factors is $s$. I'm looking for an efficient algorithm that checks the truth of the statement. Obviously one can simply ...
3
votes
1answer
157 views

Miller primality test bound

Good morning! I'm on my way to implement a deterministic (though unproven due to GRH) Miller primality test. On Wikipedia, it is said that it suffices to test all numbers in $[2, ...
1
vote
1answer
130 views

Prime asymptotics from Euler product

It is said that the Euler product $$\prod_p \frac{1}{1-p^{-s}}$$ diverges as $s \to 1^+$ proves we can't find constants $C$,$\theta$ with $\theta < 1$ such that $\pi(x) < C x^\theta$ because ...
10
votes
3answers
356 views

Are there any Combinatoric proofs of Bertrand's postulate?

I feel like there must exist a combinatoric proof of a theorem like: There is a prime between $n$ and $2n$, or $p$ and $p^2$ or anything similar to this stronger than there is a prime between $p$ and ...
2
votes
2answers
79 views

Power equivalence in a prime modulus

Given, $p,q$ primes, $x$, $c$, $(p-1)/c$ integers and $$x^{(p-1)/c} \equiv 1\pmod{p}$$ how can I show there exists a $q$ such that $$q^c \equiv x\pmod{p}$$
1
vote
2answers
153 views

Another prime inquiry: how many primes from 1 to *k*?

With the question I made about primes, I noticed people enjoy the subject, so here's another thought: let k be a positive integer; how many primes are there from 1 to k? There's probably no exact ...
1
vote
2answers
136 views

Moving powers in a prime modulus

Suppose I have $$x^{(c(p-1))} \equiv y^{(p-1)} \pmod{p}.$$ I would like to take the (p-1) root of both sides to get: $$x^c \equiv y \pmod{p}$$ I really just want to know if this a valid technique and ...
12
votes
1answer
335 views

Primey Pascal's Triangle

Imagine that we have a triangle that starts with 2,3 and grows like Pascal's triangle but instead uses the smallest prime $\geq$ to the sum of the above two primes. Visually: $$ ...
13
votes
1answer
816 views

Is there a prime number between every prime and its square?

For each prime number $p$, is there always an other prime number between $p$ and $p^2$ ? I tested it for prime numbers $< 500,000,000$, but I wanted to know if there is any mathematical proof of ...
6
votes
4answers
354 views

Prime Appearances in Fibonacci Number Factorizations

Okay, THIS one is considerably more analytical... :P (Used my post here as a basis.) When successive Fibonacci numbers are factored, the primes appear in a specific order, which goes $2, 3, 5, 13, 7, ...
2
votes
0answers
160 views

$n$ by $n$ Primally Magic Squares

(Again copied verbatim from a September 2009 thread I made.) A Primally Magic Square (PMS) is exactly like a traditional magic square with a change of criteria. Where a traditional magic square is ...
10
votes
1answer
303 views

Primes of the form 1..1

For $n \ge 1$ an integer, let's denote $u_n = \sum_{k = 0}^{n-1} 10^k$ That is $u_1 = 1$, $u_2 = 11$, $u_3 = 111$, $u_4 = 1111$, ... My question is the following : Which of them are prime numbers ? ...
4
votes
2answers
201 views

Is prime number defined to be some natural number or integer

In number theory, is prime number usually defined to be some natural number or some integer, i.e., must it be positive or can it be either positive or negative? Thanks and regards!
6
votes
5answers
765 views

Can this number theory MCQ be solved in 4 minutes?

The Problem: ( 270 + 370 ) is divisible by which number? [ 5, 13, 11 , 7 ] Using Fermat's little theorem it took more than the double of the indicated time limit. But I would like to solve it quickly ...
12
votes
2answers
771 views

nth powers modulo all primes

Let $a \in \mathbb{Z}$, $n \in \mathbb{N}^*$ be integers, and set $P=X^n - a$. Let us consider the three following statements : 1) $P$ has a root in $\mathbb{Z}$ (i.e. $a$ is an nth power) 2) $P$ ...
20
votes
4answers
1k views

Prime numbers stretch to infinity, but what about the distance between them?

That is, let $p_n$ be the nth positive prime number. Does $$L = \lim\limits_{n \to \infty} \left( p_{n+1} - p_n \right)$$ equal infinity?
2
votes
3answers
1k views

About the factors of the product of prime numbers

If a number is a product of unique prime numbers, are the factors of this number the used unique prime numbers ONLY? Example: 6 = 2 x 3, 15 = 3 x 5. But I don't know for large numbers. I will be using ...
5
votes
4answers
404 views

Show that $q(n)=11n^2 + 32n$ is a prime number for two integer values of $n$

Let $n$ be an integer and show that $q(n)=11n^2 + 32n$ is a prime number for two integer values of $n$, and is composite for all other integer values of $n$.
6
votes
2answers
685 views

Infinite Prime Proof Using Euler's Totient

I need something explained or corrected: In my number theory class we proved that there are an infinite number of primes using Euler's Phi Totient. It went something like this: Let $M = p_1 p_2 ...
2
votes
5answers
354 views

Best method to calculate an unknown prime

I'm struggling with primes... I want to create a calculation program which need to check a number to be prime. No problem so far! The problem starts when this number exceeds 48 million. The way my ...
4
votes
2answers
186 views

Are there distinct primes $p,q$ satisfying $pq=(2^r-1)(p+q)-5$?

We let $p\neq q$ be odd prime numbers and $r$ be integer $>2$. Are there such $p,q$ satisfying $pq=(2^r-1)(p+q)-5$? This is clear from here that, $q(p-2^r+1)=(2^r-1)p-5$, and ...
5
votes
3answers
2k views

What is the most efficient algorithm to find the closest prime less than a given number $n$

Problem Given a number n, $2 \leq n \leq 2^{63}$. $n$ could be prime itself. Find the a prime $p$ that is closet to $n$. Using the fact that for all prime $p$, $p > 2$, $p$ is odd and $p$ is of ...
3
votes
2answers
322 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
250 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
372 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
661 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
201 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
99 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 ...
125
votes
6answers
23k 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
277 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
293 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
235 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
244 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
985 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
793 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 ...
45
votes
2answers
5k 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 ...
9
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
212 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
316 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
264 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
209 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
518 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 ...
15
votes
2answers
2k 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?