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
1answer
22 views

How to formally write $f\left(k\right)={1\over p_1}+{1\over p_1p_2}+{1\over p_1^2p_2p_3}+{1\over p_1^4p_2^2p_3p_4}+\dots$

How do I write the following finite series as a sum of products: $$f\left( k \right) = {1 \over p_1} + {1 \over p_1p_2} + {1 \over p_1^2p_2p_3} + {1 \over p_1^4p_2^2p_3p_4} + \dots + {1 \over ...
0
votes
1answer
28 views

How to formally write $f\left(k\right)={1\over p_1}\left(1+{1\over p_2}\left(1+{1\over p_3}\left(1+\dots\right)\right)\right)$

How do I write the following finite series as a sum or product: $$f\left(k\right) = {1 \over p_1} \left(1 + {1 \over p_2} \left(1 + {1 \over p_3}\left(1+\dots \right) \right) \right)$$ …all the way ...
1
vote
1answer
27 views

Asymptotic behavior of $\pi (x)-\frac{x}{\log x}$

What is the asymptotic behavior of the function given below. $$f(x)=\pi (x)-\frac{x}{\log x}$$ $$f(x)=O(g(x))$$ What can be $g(x)$? Also what is the asymptotic behavior of the $h(x)=f(x)-g(x)$. My ...
1
vote
2answers
34 views

Solving for a random number less than 401, generated by multiplying two numbers less than 21.

So, at a math meeting tonight we decided to play a game where you try to solve for a random number between 1 and 400 generated by multiplying two numbers between 1 and 20 together. Basically the ...
3
votes
1answer
45 views

Squares modulo 2^n

How many squares are there modulo $2^n$? If we would deal with $p^n$, where p an odd prime, then we could use Hensel's Lemma, which clearly doesn't work with $2^n$.
2
votes
1answer
19 views

Error term of the prime number theorem in arithmetic progressions

It is known that if $(a, q)$ and $q\le (\ln x)^N$, then the following is true $$\sum_{k\le x, k\equiv a\pmod{q}}\Lambda(k) = \frac{x}{\phi(q)} + O(x\exp(-C\sqrt{\ln x}))$$ where $C$ depends only on ...
2
votes
0answers
18 views

Minimum degree of polynomial assuming exactly k prime values

Dirichlet's theorem states that there are infinitely many primes of the form $an+b$ for coprime integers $a$ and $b$. This implies that The minimum degree of a polynomial $f \in \mathbb{Z}[X]$ ...
1
vote
1answer
30 views

show that there is some element x∈X whose stabilizer Gx is all of G where G is a group of order p^k, where p is prime and k is a positive integer

I'm having trouble with this problem: Suppose that G is a group of order p^k, where p is prime and k is a positive integer.
-1
votes
0answers
28 views

Every prime of the form 4n+1 can be written as sum of two squares which are unique for each 4n+1 prime [on hold]

Prove that every prime of the form 4n+1 can be written as sum of two squares and the choice of the two squares, one even and one odd is unique for each 4n+1 prime.
0
votes
1answer
35 views

Find the natural numbers so that n=2*a^2 ,n=3*b^3 ,n=5*c^5.Number theory problem.

Well here it is i spend almost 3 hours on this one!! Find the general form of the natural numbers that are twice a square ,tripple of a cube and 5 times a 5-ith power.Who is the smaller of them?.What ...
10
votes
9answers
816 views

A Poster About Prime Numbers [on hold]

We're going to design a poster about prime numbers, which will appear in a mathematics magazine for middle school students. The poster should be both visually attractive and mathematically rich. Do ...
-1
votes
0answers
75 views

Proof for the existence of infinite integer $n$ such that $n^2 = p + 8$ (where p is some prime) [on hold]

Prove that there exist an infinite number of integers $n$ for which $n^2=p+8$ for some prime $p.$ -MKA
1
vote
2answers
18 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
14 views

Group of numbers with common euler's totient function result [duplicate]

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 ...
2
votes
2answers
131 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
32 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
42 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
75 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 ...
1
vote
0answers
36 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 ...
6
votes
1answer
132 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
22 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 ...
5
votes
1answer
109 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
45 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$.
3
votes
4answers
271 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 ...
0
votes
2answers
29 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
24 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
52 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
21 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 ...
6
votes
1answer
42 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 ...
2
votes
1answer
21 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 ...
0
votes
2answers
18 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
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 ...
0
votes
0answers
20 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
1answer
125 views

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

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 ...
1
vote
1answer
46 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 ...
3
votes
0answers
87 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, $x^2-py^2=-1$ has no solution in integers. Thanks a lot!
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
62 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. : ...
2
votes
1answer
66 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
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
40 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
1answer
43 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 ...
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 ...
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
1answer
23 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 ...
0
votes
1answer
78 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} ...
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 ...
0
votes
1answer
49 views

Explain theorem in Number theory

can some one explain with a clear example this theorem for me, Let ($A_1$, $A_2$, $A_3$,..., $A_n$) be integars and $p$ a prime number. if $p|(A_1A_2A_3...A_n)$ then there exist some $1 \leq k \leq ...