Questions tagged [prime-numbers]

Prime numbers are natural numbers greater than 1 not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

Filter by
Sorted by
Tagged with
6
votes
1answer
1k views

Maximum order of integers coprime to a prime $p$

The following is a lemma I read online, but I don't understand part of the proof. Let $d$ be the maximum possible order among integers $a$ prime to $p$. Then for any integer $a$ not divisible by $p$,...
4
votes
1answer
556 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 ...
4
votes
2answers
266 views

How to prove this inequality using prime number theorem

Define $s_n=p_{n+1}-p_n$, where $p_n$ is the $n$th prime number, now how to show that $$\lim_{n \rightarrow \infty} \inf \frac{s_n}{\log n} \leq 1$$ I used the result from the prime number theorem: $...
2
votes
2answers
89 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}$$
8
votes
2answers
514 views

A limit involving prime numbers

Me and a friend of mine worked on building a problem for AMM. It all started pretty well, but in the end we realized that the initial part of the solution was wrong. In few words, we thought we have ...
3
votes
1answer
159 views

For a prime $p$, determine the number of positive integers whose greatest proper divisor is $p$

I'm having a bit of difficulty writing a graceful proof for the following problem: For a prime $p$, determine the number of positive integers whose greatest proper divisor is $p$. Let $A$ be the ...
2
votes
1answer
191 views

With what probability is this polynomial equal to zero (mod a prime $p$)?

If we suppose that we have a polynomial $q(x)$ of the following form: $q(x) = \sum_{i=0}^N{c_i x^i} \text{ where } c_i=0 \text{ or } c_i=1$ In other words, if we are given a polynomial with binary ...
4
votes
2answers
250 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!
1
vote
2answers
527 views

The highest power of a prime that divides $f(x)$

I have read a result on computing the highest power of a prime that divides $n!$. I was wondering if there are any results on how to compute the highest power of a prime dividing $f(x)$, where $f$ is ...
2
votes
1answer
202 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 ...
1
vote
0answers
122 views

lower bounds for maximum computing times for integer factorisation

Supposing that n were known to have two prime factors, and that the computer had a database of all the primes $<\sqrt{n}$. Then, unless n is square, one factor would be $<\sqrt{n}$. If an ...
34
votes
3answers
1k views

Sequence of numbers with prime factorization $pq^2$

I've been considering the sequence of natural numbers with prime factorization $pq^2$, $p\neq q$; it begins 12, 18, 20, 28, 44, 45, ... and is A054753 in OEIS. I have two questions: What is the ...
12
votes
5answers
328 views

Is there a single or best reason that 2 is an exceptional prime?

I've recently been studying some elementary number theory, and I've frequently come across the fact that there are a fair number of results (the main one being the law of quadratic reciprocity) for ...
3
votes
2answers
2k 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. $(1+ap)^{p^{...
3
votes
2answers
841 views

Set of prime numbers and subrings of the rationals

Let $P$ denote a set of prime numbers and let $R_{P}$ be the set of all rational numbers such that $p$ does not divides the denominator of elements of $R_{P}$ for every $p \in P$. If $R$ is a subring ...
7
votes
2answers
1k views

Prime factors of $n^2+1$

I know it is unknown if there are infinitely many primes of the form $n^2+1$. Is it known if there is a positive integer $k$ such that $|\{n\in\mathbb{Z}:n^2+1 \text{ has at most k prime factors}\}|=\...
5
votes
1answer
3k 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 $...
2
votes
2answers
316 views

How to show that $n$ is a prime?

Suppose that $n>1$ satisfies $(n-1)! \equiv -1 \pmod n$. Show that $n$ is a prime. (Hint: Antithesis) My own trying: $n=3$: $(3-1)!+1= 3 \cdot 1$ => $3|2!+1$. $n=5$: $(5-1)!+1=25 = 5 \cdot 5$ => $...
7
votes
2answers
2k views

lower bound for the prime number function

Does there exist a function $f$ that is a lower bound of the prime number function $\pi$ with $f \sim \pi$?
2
votes
2answers
9k 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 \...
1
vote
2answers
147 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 ...
3
votes
1answer
845 views

Prime congruence

If $p\equiv3\pmod{4}$ and $q=2p+1$ is a prime then $q|(2^p-1)$ if $2^p-1$ is composite. Also, prove that there are infinitely many primes $p$ for which $2^p-1$ is composite.
1
vote
3answers
342 views

Number of factors of Carmichael numbers

Hello world! Now I'm implementing a stochastic (k-rounded) Fermat primality test for my annual scientific work. I know it is ...
1
vote
2answers
898 views

Ratio of primes

How can one find the limit as M approaches infinity of the ratio of the number of primes p to the number of primes q all less then M. Where every p satisfy: p+42 is prime, and p+20 is prime. And ...
3
votes
1answer
150 views

Formula for likely prime

Numbers of the form $n!+1$ are quite often prime numbers. Is there any formula $f(n)$ such that the probability that $f(n)$ is prime approaches 1 as $n$ goes to infinity and $f(n)$ also approaches ...
4
votes
3answers
136 views

Given $a$, $b$, and a prime $p$, how fast can we solve $(a \cdot c) - (b \cdot d) \equiv 1 \bmod p$?

If we're given two naturals, $a$ and $b$, and a prime $p$, how fast can we find two more naturals such that $(a \cdot c) - (b \cdot d) \equiv 1 \bmod p$? Additionally, you are allowed to precompute ...
2
votes
2answers
444 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.
10
votes
0answers
636 views

Sums of Dirichlet-Characters over prime numbers (part 2)

This is kind of related to my previous question that was poorly stated because of misreading my own notes that I have taken on the papers I am currently reading, so no surprise that it eventually ...
3
votes
3answers
1k views

How to check if an integer has a prime number in it?

Is there any way by which one can check if an integer has a prime number as a subsequence (may be non-contiguous)? We can check if they contain the digits 2,3,5 or 7 by going through the digits, ...
9
votes
1answer
431 views

Asymptotics of sums of Dirichlet-Characters over prime numbers

Again in relation with some stuff I am currently reading, the authors make use of the following "standard argument in prime number theory": Let $\chi$ be a non-principal Dirichlet-character. Then $$\...
1
vote
3answers
1k views

Can we use Peano's axioms to prove that integer = prime + integer?

Every integer greater than 2 can be expressed as sum of some prime number greater than 2 and some nonegative integer....$n=p+m$. Since 3=3+0; 4=3+1; 5=3+2 or 5=5+0...etc it is obvious that statement ...
25
votes
4answers
3k views

Proof that there are infinitely many prime numbers starting with a given digit string

To prove the following fact: given any sequence of digits in any base, eg 314159265358979323 base 10, there are infinitely many primes that start with these digits,eg when expressed in decimal they ...
3
votes
1answer
324 views

If a prime with prime norm is a split prime, in the number ring PID

If a prime with prime norm is a split prime , in an number ring PID? Example: $5-\sqrt{14}$ in $\mathbb{Z}[\sqrt{14}]$ has norm $11$, it is a split prime in $\mathbb{Z}[\sqrt{14}]$? Why? Thanks
4
votes
1answer
4k views

Factoring large integers without a cluster

What is the best program to factor large arbitrary-form integers on a single computer, or on a few disjointed computers? "Best" is obviously subjective, but what do you recommend? I'm working on a ...
10
votes
2answers
932 views

Showing the equivalence of two forms of the Goldbach Conjecture

My number theory textbook has the following (paraphrased) exercise: Goldbach wrote a letter to Euler with the following conjecture: Every integer greater than five can be written as the sum of three ...
4
votes
1answer
314 views

How to find primes between $p$ and $p^2$ where $p$ is arbitrary prime number?

What is the most efficient algorithm for finding prime numbers which belongs to the interval $(p,p^2)$ , where $p$ is some arbitrary prime number? I have heard for Sieve of Atkin but is there some ...
4
votes
2answers
349 views

What's wrong with my proof of infinitely many primes of the form $am+b$, $\gcd(a, b) = 1$

So the prof said in class that the proof of this is hard, but we might want to attempt at home. I won't be able to see him again until Wednesday, but I'm guessing there is some hole in my proof, since ...
2
votes
1answer
2k views

Even numbers greater than 6 as sum of two specific primes

It is well known fact that it is very hard to prove Goldbach's strong conjecture but perhaps some weaker variations can be proved ,so my question is: Is it true that every even number greater than 6 ...
5
votes
3answers
669 views

Powers as a complete residue system modulo $p$?

Question 1. With $0 < a < p$, $p$ prime and $\gcd(a,p-1)=1$, is it true that $0, 1, 2^a, ...,(p-1)^a$ is a complete residue system modulo $p$? If not, will a similar statement hold? Question ...
10
votes
2answers
273 views

Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime?

Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime? While answering @pedja's question about the existence of any such representations I was ...
1
vote
0answers
158 views

Infinite number of primes in the sequence $1+t^2$? [duplicate]

Possible Duplicate: Primes of the form $n^2+1$ - hard? $1, 2, 5, 10, 17, \ldots$ Are there an infinite number of primes in this sequence $1 + t^2$, $t$ being an integer?
4
votes
1answer
4k views

Even numbers greater than 10 as sum of two specific odd numbers

It is well known fact that it is very hard to prove Goldbach's strong conjecture but perhaps some weaker variations can be proved(or disproved) ,so my question is: Is it true that every even number ...
12
votes
1answer
464 views

primegaps w.r.t. the m first primes / jacobsthal's function

Maybe I don't see the obvious here; but well. I looked at an old discussion concerning prime gaps. I now tried to ask a somehow opposite way: Assume the set $\small P(m)$ of first m primes $\small \...
1
vote
1answer
171 views

Checking if all elements are prime

I've often come across problems where (as a subproblem) I need to decide whether a list of numbers contains only primes or at least one nonprime. Is there an efficient way to do this? Right now I ...
2
votes
1answer
2k views

Where can I find a list of sphenic numbers?

According to Wikipedia, A Sphenic number is a positive integer which >is the product of three distinct prime numbers. Anybody knows whether there is a list, say first 1000 sphenic numbers? It ...
2
votes
2answers
135 views

Estimating number of crossings for Erastothenes' Sieve

In this paper (2.1) I need to understand the formula for the total number of operations: $$\sum_{i=1}^{\pi(\sqrt n)}\frac{n}{p_i} \approx n\ln \ln n + O(n)$$ On a sidenote, since we're only checking ...
17
votes
2answers
2k views

sums of square free numbers , is this conjecture equivalent to goldbach's conjecture?

As one can notice every integer greater than $1$ is a sum of two squarefree numbers.(numbers that are not divided by some prime square power). Can we prove that? Edit: Can we have bounds for the ...
0
votes
3answers
430 views

Do there exist any dormant primes?

Suppose that n is an integer > 1 such that: The prime factorization of n is known It is known that (n + 1) is a prime Then: What can be concluded? Among the possibilities are the following: We can ...
0
votes
2answers
174 views

Conjecture about the set of Sphenic numbers

Sum of a set of sphenic numbers can't be equal to the sum of any other set of sphenic numbers. By that I meant, Say S is the set of sphenic numbers. Let S$_1$ $\subset$ S. Then there is no such S$_2$ ...
5
votes
1answer
1k views

One line Proof of the Prime Number Theorem

Whenever I am not doing anything, I generally happen to see pages of some good Mathematical Institutes in India, so as to know more about the faculty members and see what they are working on. While ...