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

0
votes
2answers
18 views

Congruence Proof Involving Fermat's Little Theorem

Let $n \in\mathbb N$. Use Fermat’s little Theorem to show that if a prime $p$ divides $n^2 + 1$, then $n^{p−1} \equiv 1 \pmod p$. So far, I have written that I need to show $n^2 \equiv -1 \pmod ...
0
votes
0answers
14 views

Prove or disprove the inequality on $p_n$

If $p_n$ denotes the $n$-th prime then is it true that, $$1>\left(\dfrac{p_{n+1}}{\ln p_{n+1}}-\dfrac{p_n}{\ln p_n}\right)$$ for all sufficiently large $n$. It seems that the inequality is very ...
4
votes
0answers
65 views

Combinatorial prime problem

Update As Barry Cipra noted in the comments, a better framing of the question might be that I'm looking at differences $a−b$ for $5$-smooth numbers $a$ and $b$ satisfying the conditions ...
0
votes
1answer
43 views

Combinatorial prime puzzle

Is it true that no prime larger than $241$ can be made by either acting or subtracting $2$ coprime numbers made up out of the prime factors $2,3,$ and $5?$ Update Above example is clearly wrong, as ...
-4
votes
3answers
50 views

$p$ is prime number $\implies f(p)$ is prime number. [on hold]

I am in search of function $f$ that satisfies the following $f\colon \mathbb{P} \rightarrow\mathbb{P}$ and it should always satisfy the following implication. $p$ is prime $\implies f(p)$ is prime ...
0
votes
1answer
14 views

Primality Test for Safe Primes

Is this proof acceptable ? Theorem Let $N$ be of the form $N=2p +1$ with $p$ prime , then $N$ is prime iff $N \mid 2^{2p}-1$ Proof In one direction , if $2p+1$ is a prime then by Fermat ...
6
votes
1answer
74 views

Prime number conjecture

It was suggested that I put my full conjecture up instead of specific examples. Here it is: Given any prime p>3, there exists c such that the following conditions hold: 1a. The quadratic equation ...
0
votes
0answers
23 views

Estimate, using the Knuth-Trabb-Pardo table, how many values of $r$ would be needed in order to factor…

Use the Knuth-Trabb-Pardo table to estimate, for the original Quadratic Sieve, with all $r \ge \sqrt{n}$, approximately how many values of $r$ would be needed in order to factor a forty-digit ...
0
votes
1answer
65 views

Are there smaller orders (cardinalities) of infinity?

I am using this source as a basis for the language to ask this question. Considering the topic of degrees of infinity, are there smaller degrees than ℵ0 (aleph null, also called ω)? ...
1
vote
1answer
35 views

In $\mathbb{Z}_q$ where $q$ is prime, show that $[a^q]=[a]$ for all $[a]\in \mathbb{Z}_q$

Question: In $\mathbb{Z}_q$ where $q$ is prime, show that $a^q=a$ for all $a\in \mathbb{Z}_q$. My attempt: To show $[a^q]=[a]$ for all $[a]\in \mathbb{Z}_q$, it suffices to show that for any ...
1
vote
1answer
39 views

Consecutive prime numbers

Let's assume k and n are consecutive prime numbers, $k \lt n$. An axiom: for any such $k$ and $n$, $k^2 \gt n$. This seems 'obviously' true to me, but could you please prove me wrong? Or if it's ...
0
votes
0answers
28 views

Triangular number puzzle with big numbers

Let $n_T$ be the $n^{th}$ triangular number, 1+2+3+...+n or $\sum_{i=1}^n i$ , which equals ${n(n+1) \over 2}$ . Show there exists some positive integers m and c, such that the following are true: ...
1
vote
1answer
38 views

A question about the product of primes

Let $\mathbb{P}$ be the set of all primes in the natural numbers and let $p_i \in \mathbb{P}$ be the $i$th prime, $p_1=2$. Let $m = \prod_{i=1}^n (p_i)$. How many solutions does $x^2 + x \equiv 0 ...
0
votes
1answer
40 views

A question on the prime number theorem as presented in the following paper

In the section 2. of this paper it is written that, ...The prime number theorem ensures that we can choose $B$ as close to $1$ as we want, provided $x_0$ is sufficiently large. I think that ...
1
vote
1answer
31 views

Irrationality of Decimal Expansion of Primes

I've heard the proof that this number is irrational is accessible to even a novice to number theory: $\alpha = 0.2 \ 3 \ 5 \ 7 \ 11 \ 13 \ 17 \ldots$ The proof may utilize that a number is ...
2
votes
1answer
42 views

Periodicity over the prime indices of a multiplicative sequence implies periodicity?

I have a real sequence $(a_p)$ indexed by the prime numbers which takes values -1, 0, or 1, having the property that $a_p=a_q$ whenever $p\equiv q \pmod m$, where $m$ is a fixed integer $>2$. I'm ...
6
votes
1answer
86 views

A conjecture concerning primes and algebra

A monoid morphism $\psi:\mathbb Z_+\!\!\rightarrow\mathbb Z_+$ is defined by an arbitrary function $f:\mathbb Z_+\!\!\rightarrow\mathbb Z_+$ and defines a group homomorphism $\varphi:\mathbb ...
4
votes
0answers
58 views
+50

How many numbers are products of $p^p$?

Consider the set $\mathcal{S}=\{1,4,16,27,\ldots\}$ of numbers which are products of numbers of the form $p^p$ for $p$ prime. ($\mathcal{S}$ is A072873 in the OEIS.) Note that multiple primes are ...
1
vote
1answer
54 views

To prove $\pi(x)>\dfrac x{\ln x} , \forall x \ge 17$ by elementary argument

Is there an elementary argument for proving $$\forall x \ge 17:\pi(x)>\dfrac x{\ln x} $$ ? where $\pi(x)$ is the prime counting function ....
5
votes
0answers
77 views

Primality of $n! +1$

I came across with a problem where I was required to examine primality of $n! +1$ (17! + 1 was the actual number). Although Wilson's Theorem could be manipulated for determining primality of $n! + ...
0
votes
1answer
13 views

finding A using with restriction $1 \leq a \leq 20$ in GCD

For what $1 \leq a \leq 20$ you are finding $a$ is it true that $a^m+a^n=x^2$ for positive integers $a,m,n,x.$ I did $a^m+a^n=x^2.$ $=a^m(a^{n-m}+1)=x^2$ We know that since $(a,b)=1$ since the ...
-3
votes
3answers
40 views

Prove that product of two primes is 1 less than a perfect square of a multiple of 6 except for (3,5) [on hold]

Prove that product of two primes is 1 less than a perfect square of a multiple of 6 except for (3,5).
0
votes
0answers
8 views

Primality Criterion for Specific Class of Proth Numbers

Is this proof acceptable ? Theorem : Let $N = k\cdot 2^n+1$ with $n>1$ , $k<2^n$ , $3 \mid k $ , and $\begin{cases} k \equiv 3 \pmod {30} , & \text{with }n \equiv 1,2 \pmod 4 \\ k ...
-1
votes
1answer
25 views

Asymptotic Expression for the Twin Prime Counting Function

A variation on a previous question I asked, which has garnered no responses. I'll attempt to be more lucid: Let $\pi_2(x)$ be the twin prime counting function and $\pi(x)$ be the prime counting ...
-1
votes
0answers
15 views

Relationship between density of twin primes and super-primes?

One can define the twin prime counting function as $\pi_{2}(x) = \sum_{n=3}^{x} a_n$ where $a_n = [\pi(n) - \pi(n-1)][\pi(n+2) - \pi(n)]$ and the super-prime counting function as $\pi_{s}(x) = ...
0
votes
0answers
49 views

How can one find a million of consecutive prime numbers greater than 1 trillion? [duplicate]

I am looking for bigger prime numbers than 1 trillion. At least a million consecutive ones. Where or how can I find some?
0
votes
1answer
32 views

A Generalization of Carmichael Numbers

Obviously, from Fermat's Little Theorem, the condition of $p$ being prime is equivalent to there being some number $a$ of multiplicative order $p-1$ mod $p$. Moreover, this is equivalent to saying ...
0
votes
2answers
19 views

Proof for divisions that in include prime number. [duplicate]

How do I prove, that if $m^2$ can be divided $p$ (where $m$ is a whole number and $p$ is a prime number) then also m can be divided by $p$?
3
votes
6answers
2k views

If $p$ and $q$ are prime numbers larger than $2$, then $pq + 1 $ is never prime

I am trying to prove the following: If $p$ and $q$ are prime numbers larger than $2$, then $pq + 1 $ is never prime. Any ideas?
2
votes
2answers
123 views

Prove or disprive that $n^{2}-n+17$ is prime for all integers $n$

I am looking to prove this function is always prime for all integers $n$: $$n^{2}-n+17$$ I have tested it for the first $10$ integers and it seems to work but I am not sure how to prove it form all ...
0
votes
1answer
28 views

The primes such that removing digits from the right end leaves another prime

The number 73,939,133 is prime. Keep removing a digit from the right end. Each of the remaining numbers is prime. How to find other numbers with this property?
2
votes
0answers
16 views

Does there exist a sequence $(S_i)_{i=1}^{\infty},\ S_i=\pm1$ such that $\forall i(2+S_1g_1+S_2g_2+\cdots+S_ig_i\in\Bbb P)\wedge\exists i:S_i=-1$?

Consider a sequence $(S_i)_{i=1}^{\infty},\ S_i=\pm1$ other than $\{1,1,\ldots\}$. Let $g_i=p_{i+1}-p_i$, where $p_i$ is the $i$th prime. Is it possible that for all $k\in\Bbb Z^+,\ ...
1
vote
1answer
10 views

Does there exist a positive integer $k$ such that $(g_i^k)_{i=1}^{\infty},\ g_i^k=p_{i+k}-p_i$ is non-decreasing for all sufficiently large $i$?

Does there exist a positive integer $k$ such that $(g_i^k)_{i=1}^{\infty},\ g_i^k=p_{i+k}-p_i$ is non-decreasing for all sufficiently large $i$, where $p_i$ is the $ith$ prime? $g_{i+1}^k\geq ...
4
votes
2answers
62 views

Generalisations of primes

I've read of (normal) primes, Gaussian primes and Eisenstein primes, which all uses different ways to define an integer to be a prime. For instance, $2$ factors into $1-i$ and $1+i$ for guassian ...
12
votes
1answer
90 views

Consequences of the negation of the Riemann hypothesis

There are many sources documenting the consequences of the Riemann hypothesis, but I can't find one discussing the consequences of its negation, particularly concerning the prime distribution.
1
vote
2answers
33 views

Prove that if p divides xy then p divides x or p divides y

I am given that the following proposition is true. (Proved in class) "Suppose that $x$, $y\in \Bbb Z$, not both zero. Then there exists $m$, $n\in\Bbb Z$ such that $$mx + ny = d$$ where $d$ is the ...
1
vote
0answers
20 views

Syndeticity and A.P.-richness of certain sets

Let $A \subset \mathbb{N}: \sum_{a \in A} (\frac{1}{a}) = \infty$; denote $\{ \alpha_1 @ \alpha_2: \alpha_1, \alpha_2 \in A \} = A @ A$, where "$@$" is any appropriate binary operator. (Note: $A$ is ...
0
votes
1answer
73 views

Prime number in set $\{1,…,60\}$

How can we calculate by using the principle of inclusions and exclusions how many prime numbers are in the set $ \{1, ..., 60 \} $?
0
votes
1answer
25 views

an irreducible polynomial over GF(2) is primitive over GF(2)

let $P \in F_{2} [X]$ of degree $7$, how to prove this: P is irreducible $\Leftrightarrow$ P is primitive i tried to use the mersenne prime !
1
vote
2answers
45 views

How can I prove that the square root of two prime numbers multiplied is non-rational number?

$P$ and $Q$ are two distinct prime numbers. How can I prove that $\sqrt{PQ}$ is an irrational number?
0
votes
1answer
22 views

Disproving using a Constructive Proof

I cannot find the n to prove the negation for the following: Disprove (Prove the negation) of: For every positive integer n, $3^n + 2$ is prime The way in which I have written the negation is: ...
3
votes
1answer
52 views

Given $0 < p < n$, prove there exists $n$ consecutive natural numbers such that each natural is divisible by at least $p$ distinct primes.

Given $0 < p < n$, prove there exists $n$ consecutive natural numbers such that each natural is divisible by at least $p$ distinct primes. Is there a general proof method to prove this ...
2
votes
3answers
70 views

Finding all the values of n, such that $ \varphi (n) = 12 $ [duplicate]

I have not broken this down very far. I have come to the conclusion that there are infinitely many values for n where there exists 12 coprimes to n. Since there are infinitely many primes, and primes ...
1
vote
0answers
30 views

Fundamental Theorem of Arithmetic (Canonical) missing crucial step

I've worked long on the proof of the fundamental theorem of Arithmetic and there is only one tiny piece left I can't wrap my head around. Suppose that $$\prod_{i=1}^r p_i^{m_i} = \prod_{j=1}^s ...
0
votes
1answer
31 views

Uses of Mersenne primes in math

There is an international search for Mersenne primes. The project is huge. But what are the uses of Mersenne Primes in math? Do they have any other properties other than being of the form $2^n-1$?
3
votes
1answer
60 views

Is this number composite or prime: $2000^{2002} + 2000^{2000} + 1$?

Is this number composite or prime? $$2000^{2002} + 2000^{2000} + 1$$ I want to find an easy approach to this problem.
5
votes
1answer
35 views

Normalizer and centralizer are equivalent when $p$ is the smallest prime dividing $|G|$

Let $p$ be the smallest prime dividing $|G|$, and suppose that some $P \in \mathsf{Syl}_p(G)$ is cyclic. Prove that $N_G(P) = C_G(P)$. So I let $G=p^\alpha m$ $p$ does not divide $m$. P is cyclic, ...
0
votes
0answers
103 views
+50

Remarks on a Previous Post

Recently I have been reading this post and I have noted something significant in the fake argument. As one can easily see that the basic idea behind the argument had been to show that the sequence ...
0
votes
1answer
41 views

Is it an open problem about Riemman Hypothesis non-trivial zero? [duplicate]

Let's assume RH was correct, and $1/2+Ki$ is any one of non-trivial zero of $\zeta$, is following problem open? 1) $K$ is irrational number 2) $K$ is transcendental number
0
votes
1answer
22 views

can Sophie Germain prime be arbitrarily many?

We know that there exists arbitrarily long prime arithmetic progressions by BEN-TAO. Together with Dirichlet's theorem on arithmetic progressions, can we address that Sophie Germain prime number be ...