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

2
votes
3answers
2k views

How to find next prime number?

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number?
1
vote
2answers
14 views

Group Theory - Prime Index

The index $(G : H)$ of a subgroup H of G is the number of cosets of H. Let H be a normal subgroup with (G : H) = p, where p is a prime, and let a be an element of G that is not in H. Show that for ...
0
votes
0answers
12 views

Group of numbers with common euler's totient function result

I was asked to find the group of integers, which share the result of euler's function of 84. To be clear: which numbers, when applying eulers function on them, result 84. By calculating I found that ...
3
votes
1answer
350 views

Super palindromes

Can anybody be kind enough to explain what exactly is a super palindrome? Also consider the following example : $923456781-123456789=799999992:9=88888888$ The largest prime factor of $88888888$ is ...
2
votes
2answers
125 views

Let q be an odd integer such that p = 4q+1 is prime.

Let $q$ be an odd integer such that $p = 4q+1$ is prime. a. Show that $(2|p) = -1$ b. Prove that $p | (4^q+1)$ So far I see that: $(2|p) = (-1)^{ (\frac{(p^2-1)}{(8)} )}$. Not sure if this helps ...
0
votes
2answers
27 views

Let p be an odd prime, q the smallest quadratic non residue (mod p). Prove q is prime.

So I have this problem; Let p be an odd prime and let q be the smallest positive integer which is a quadratic non residue (mod p). Prove q is a prime. So what I know is that, since q is the ...
1
vote
1answer
41 views

Prove the center of $G$ cannot have order $p^{n-1}$

Let $p$ be a prime, let $n>2$ be an integer, and let $G$ be a nonabelian group of order $p^n$. Prove the center of G cannot have order $p^{n-1}$. Honestly I have no idea where to start. Perhaps ...
0
votes
3answers
34 views

If G acts on X, show that there must be a fixed point for this action. Please help. [on hold]

Suppose that G is a group of order p^k, where p is prime and k is a positive integer. Suppose that X is a finite set and assume that p does not divide the size |X| of X. If G acts on X, show that ...
6
votes
1answer
126 views

Congruences and prime powers

I have just a small question that probably is not hard to answer, but I could not find and elegant solution to this question. Let $p$ and $q$ be prime numbers. $$5^q\equiv 2^q \pmod p$$ $$5^p\equiv ...
0
votes
0answers
28 views

Program for Handling Huge Primes

I am trying to run a program with really large primes (around the $10^{20}$th prime), but Mathematica seems to only be able to handle around the first $10^{12}$ primes. Is there any software that can ...
3
votes
0answers
73 views

diophantine equation $ |x^2-py^2|=\frac{p-1}{2} $

Prime $p\equiv3\pmod4$, then diophantine equation $$ |x^2-py^2|=\frac{p-1}{2} $$ has a solution in integers obviuosly, en, $x^2-py^2=-1$ has no solution in integers. Thanks a lot!
0
votes
0answers
21 views

If $k\le n$ and $k$ is relatively prime to $n$, there exists a prime $p$ such that $p \equiv k \mod n$.

I need to use this result in a step of a proof, but I am for some reason unable to justify it. It seems to be true, after trying some examples, but I am not sure why. If $1 \le k\le n$ and $k$ is ...
11
votes
4answers
2k views

Prime factorization of 1

Fundamental Theorem of Arithmetic says every positive number has a unique prime factorisation. Question: If 1 is neither prime nor composite, then how does it fit into this theorem?
5
votes
1answer
96 views

is $324+455^n$ ever prime

Another question that I can only solve in part. Is there an $n$ such that $324+455^n$ is prime? When $n$ is odd, this is false since $$ 324+455^n = (2\cdot 3^2)^2+(5\cdot 91)^n \equiv ...
4
votes
1answer
42 views

Show that $3^n-2^n\cdot 5$ is composite for infinitely many $n$

I came across this problem: Show that $3^n-2^n\cdot 5$ is composite for infinitely many $n$ and do not know how to solve it. I only know that it is true for $n=7$, since then $1547=17\cdot 91$.
2
votes
4answers
263 views

Why do we call primes, and not the number one, *the atoms of numbers*?

The fundamental theorem of arithmetic asserts that we can produce every composite number from a unique set of prime multiplicands, so long as none of those primes equals one. Consequently, some ...
6
votes
1answer
41 views

Order of groups and group elements? [duplicate]

Let G be a group and let p be a prime. Let g and h be elements of G with order p. I am wondering how I can use group theory to find the possible orders of the intersection between ...
0
votes
2answers
26 views

Composite Numbers with 1 Prime

What is the method for finding a long sequence of consecutive composite numbers that has only 1 prime? Specifically, how to find 2011 consecutive natural numbers, 1 of which is prime.
1
vote
1answer
22 views

Is a Mersenne prime always of the form $4n + 3$?

Is a Mersenne prime always of the form $4n + 3$? Examples: $M_3 = 7 = 4 \times 1 + 3$ $M_5 = 31 = 4 \times 7 + 3$ $M_7 = 127 = 4 \times 31 + 3$ $M_{13} = 8191 = 4 \times 2047 + 3$ ...
1
vote
3answers
49 views

Is a Mersenne-Prime always of the form $3n + 1$?

Examples are: $M_3 = 7 = 3\times 2 + 1$ $M_5 = 31 = 3\times 10 + 1$ $M_7 = 127 = 3\times 42 + 1$ $M_{13} = 8191 = 3\times2730 + 1$
1
vote
1answer
14 views

Prime Counting: Relationship between Chebyshev's function and the Prime counting function

How do I show that if $\psi(x)=x+O(x^{1/2}\log^2(x))$ then $\pi(x)=\int_2^x \frac{dt}{logt} + O(x^{1/2}\log x)$ Where $\psi(x)$ is Chebyshev's second function and $\pi(x)$ is the prime counting ...
1
vote
1answer
87 views

Is $(1+2+3+…)=(1+2+2^2+2^3+…)(1+3+3^2+…)(1+5+5^2+…)…$?

Are these equal? $$(1+2+3+…)=(1+2+2^2+…)(1+3+3^2+…)(1+5+5^2+…)…$$ Where the RHS has a series for each prime. Looks like they are the same series by the fundamental theorem of arithmetic. Every number ...
2
votes
1answer
18 views

Using primes to create unique character mappings for scrambled substring searching

Problem: given a string needle, and a string haystack determine if there is there an anagram of needle present as a substring of haystack? (Assume case doesn't matter). One solution is to map the ...
1
vote
1answer
40 views

Is there any prize for proving conjecture on Fermat's prime ?-+

I know this site is for mathematical questions and answer places, but I need a little help from you in some other aspect. I have searched in google but didn't get any satisfactory answer for it. This ...
2
votes
1answer
47 views

Question on the Prime Number Theorem (the Tchebychev Function) [duplicate]

This has been giving me nothing but a headache: Let the Tchebychev Function, $\psi (x)$ be defined: $$\psi (x) = \sum_{p^m \le x}\log p \space \space \space , \space \space \space p \in \mathbb P$$ ...
0
votes
2answers
16 views

On extracting primes from coprimes

Proof or disprove the following statement - There exists infinitely many $a$ and $b$ which are pair of co-prime integers , either $ab+1$ or $ab-1$ is prime. Motivation- Looking at some twin prime ...
1
vote
3answers
26 views

Factor factorials

How would you find the greatest prime factor of a factorial? For instance, 82! The 2 and 41 that are yielded when you prime-factor 82 seem to have no correlation to the prime factorization of 82!
1
vote
1answer
123 views

Consider the number $n= 2^{10^{33}} +1$ [on hold]

Consider the number $$n= 2^{10^{33}}+1$$ Suppose that it is known that none of the numbers $1 < k < 10^{6}$ divide $n$. Does it follow that n is a prime number? I know that the answer is a ...
2
votes
1answer
27 views

ON types of squarefree numbers and comparing their amounts < a given integer N.

Let an m-prime be a square-free number with m prime divisors. Also let the number of t-primes < N be represented as #(t-prime){N} (t and N being positive elements of integers). Is the following ...
4
votes
1answer
99 views

Primality of the number of obtained by concatenating the n consecutive digits

Let $f_n$ be the number obtained by concatenating the first $n$ numbers (in base 10). For example $f_1 = 1, f_3 = 123$ and $f_{13} = 12345678910111213.$ Now if $n$ is even or divisible by $5$ then ...
0
votes
0answers
18 views

How to apply the generalised divisibility rule to numbers of the form $10^k+n$

This is kind of a long question but bear with me. There's actually a question mark at the end. I'm trying to apply the generalised (decimal) divisibility rules to numbers of the form $10^k+n$ where ...
1
vote
0answers
33 views

About primes and counting them. [closed]

Are there bounds to the prime counting function that do not involve logarithms? Considering the best bounds use logarithms why is the natural logarithm so closely related to the prime counting ...
0
votes
1answer
77 views

Firoozbakht's conjecture solution?

Not so much an question as adding another level to the same question as Ratio of logarithmic primes. (See answers, same as here.) The Firoozbakht's conjecture (1982) is equal to: $$(p_{n+1})^{n} ...
1
vote
1answer
79 views

Why there are no other known Fermat primes.

Fermat primes are prime numbers of the form $2^{2^n} + 1$: $$3,~5,~17,~257,~65537$$ There are no other known Fermat primes. But why?
2
votes
1answer
33 views

Concerning types of square-free numbers and comparing sizes of their subsets.

Call a square-free a 2-prime if it has exactly two prime divisors. Call a square-free a 3-prime if it has exactly three prime divisors,etc. Does there exist an integer N > 230 such that the number of ...
12
votes
1answer
346 views

Prove that $\sum\limits_{i=0}^{k} p^{2i}$ ($p$ is prime) is never a perfect square

Prove that $$ \sum_{i=0}^{k} p^{2i} $$ where $k > 0$ and $p$ is an arbitrary prime, is never a perfect square. I think you can prove it by letting $q = \sum\limits_{i=0}^k a_ip^i$, then expanding ...
0
votes
1answer
42 views

How does this algorithm find the largest prime factor?

This question on math.stackexchange details an algorithm that can be used to find the largest prime factor of a number. I used it to solve Project Euler #3. Here's a short description of the ...
0
votes
3answers
79 views

A question on consecutive prime numbers

Prime numbers: 2 3 5 7 11 13 17 19 23 29 .... Difference between to consecutive primes: 1 2 2 4 2 4 2 4 6 .... We know that there are infinite prime numbers. This is Ok. But does the difference ...
14
votes
2answers
176 views

Conjecture: the sequence of sums of all consecutive primes contains an infinite number of primes

Starting from 2, the sequence of sums of all consecutive primes is: $$\begin{array}{lcl}2 &=& 2\\ 2+3 &=& 5 \\ 2+3+5 &=& 10 \\ 2+3+5+7 &=& 17 \\ ...
0
votes
1answer
61 views

Riemann Zeta circularity?

In this post I show: $$\prod _{p\text{ prime}} \frac{p^s}{p^s-1} = \zeta(s).$$ Wolfram Alpha shows an alternate form for the primes: $$\frac{p_n{}^2}{p_n{}^2-1}=\frac{\left(\sum _{k=1}^{2^n} ...
0
votes
0answers
25 views

A prime connection between two numbers with same prefix

If I know that the number n is prime, is there a fast algorithm to check if 10*n+k is prime, where k is 1, 3, 7 or 9? I mean, an algorithm based on the fact that n is prime. Thanks for help! P.S. : ...
0
votes
2answers
46 views

Is the following statement true

Is the following statement true and how to prove it? \begin{align} (a^2)^{3N} \equiv a^2 \mod{p} \end{align}
1
vote
4answers
38 views

solutions to linear equations involving prime numbers?

Suppose we have the two equations: $2Z - p = Xq$ $2Z - q = Yp$ where $X,Y,Z \in \mathbb{N} $ and $p,q \in \mathbb{P} - \left\{2\right\} $ Are there any solutions where $Z$ isn't prime?
0
votes
2answers
197 views

find a general expression for the remainder when a prime divides a fibonacci.

I have primes of form $5k\pm1$. Consider the equation: $F_n=f(n)\pmod p$ where $F_n$ is the nth fibonacci number. Now given a c, how can i check whether or not there exists a solution for $f(n)=c ...
1
vote
1answer
53 views

Coprimality of $2^n + 3^n$ and $5^n + 7^n$

Prove or disprove that for all positive integers $n$, $2^n +3^n$ and $5^n + 7^n$ are always coprime. This is not a homework problem, it is merely a problem I set myself after doing some number theory ...
0
votes
1answer
22 views

Dirichlet prime counting function?

Let $a$ and $b$ be coprime (i.e. $a \perp b$). Let $f(a,b,x)$ denotes the number of the primes such that $p=ak+b$ and not greater than $x$. For example $f(4,1,10)= 1$. Is there an asymptotic formula ...
2
votes
1answer
32 views

Is there a asymptotic formula for product of primes? [duplicate]

$$P(x)=\prod_{p\leq x}p$$ As you can see P(x) represents the product of primes which are not greater than x. Is there a asymptotic formula for this?
0
votes
0answers
261 views

New method derived out of Fermat's factorization method

Let us take two examples: a) $N=943=41*23=(\frac{41+23}{2})^2-(\frac{41-23}{2})^2$ but if we take $B=\frac{N+1}{4}$ then we can represent it as $B={x}^2-({y}^2+y)$ and in our case: ...
0
votes
1answer
47 views

infinite primes $p\equiv1\pmod n$ without cyclotomic polynomial

Without cyclotomic polynomial, is there an elementary proof of the following: for each integer $n>1$, there are infinitely many primes $p$ such that $p\equiv1\pmod n$ ? please don't refer to ...
3
votes
2answers
66 views

Ratio of logarithmic primes

Any help is appreciated in proving/disproving the following inequality $$ \frac{\ln{p_{n+1}}}{\ln{p_{n}}} < \frac{n+1}{n} $$