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
0answers
57 views

Why are academic topics in mathematics so far away from real concrete mathematics? [on hold]

Academic mathematics seems to eat for breakfast zeta functions and Mellin transforms while in reality, the zeta function is only a heavy notation for the lexicographic order of the prime factorization ...
0
votes
0answers
11 views

About a Variant of Ulam Spiral

Here I read about a variant on the Ulam spiral: [A] structure may be seen when composite numbers are also included in the Ulam spiral. [...] Using the size of the dot representing an integer ...
1
vote
1answer
30 views

Random conjecture

For any numbers $a$ and $b$ so that $a>b$ and $\text{gcd}(a, b)=1$, there exists a $c\in\mathbb{N^+}$ so that $a+bc$ is prime. I've only just tested this out with a few numbers, but I'm curious as ...
0
votes
0answers
5 views

Size of the “fixed” terms in the prime k-tuple conjecture

The prime $k$-tuple conjecture predicts that for $(a_{1}n + b_{1}), \ldots, (a_{k}n + b_{k})$ an "admissible" k-tuple, where the $a_{i}, b_{i}$'s are fixed, then there are $$ \sim c ...
6
votes
0answers
42 views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
0
votes
1answer
24 views

Median primes and cryptography

I've been considering something involving median numbers. If an integer is directly in the middle of two integers, is it possible to accurately extrapolate what two it is between? Can a prime be in ...
1
vote
0answers
24 views

Solutions to $3\cdot 5 p_1 \pm 37^n p_2 =2\cdot 29^m p_3$

Let $p_k$ be either primes larger than $40$ or equal to $1$. $n,m$ are larger than $0$ and $b$ is either $1$ or $2$. I'm searching solutions for the following equation: $$ 3\cdot 5 p_1 \pm 37^n p_2 ...
0
votes
0answers
31 views

Existence of a prime in an interval that is not a linear combination of two specified primes?

If $ n = \left( \frac{p+q}{2 } \right) + p q :p,q \in\mathbb{P}-\left\{2\right\} $ Can we show there exists a prime number $\theta : \sqrt{2n} \leq \theta \leq n $ and $\theta$ is not a linear ...
1
vote
1answer
27 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
30 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
42 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 ...
4
votes
2answers
57 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
21 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
32 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
30 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
37 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
823 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
77 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
133 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
76 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
112 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
46 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
276 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
22 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
23 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
20 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
92 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 en, $x^2-py^2=-1$ has no solution in integers. I'd be grateful for any help you are ...
1
vote
0answers
34 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
26 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
69 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}