0
votes
2answers
123 views

$9n^2-4$ only generates one prime? Why?

Instead of doing the work I was supposed to be doing, I played around with some numbers, and I noticed that for $n\in\mathbb{N}$, $9n^2-4$ only seems to generate a prime for $n=1$. Can anyone ...
0
votes
4answers
108 views

Is at least one of $6k + 1$ or $6k-1$ prime?

We know that any prime number ( $> 2,3$) can be written in the form $6k+1$ or $6k-1$. Is it necessary that at least one of $6k+1$ or $6k-1$ is a prime number ?
0
votes
0answers
38 views

Fast check of safe primes or Sophie Germain primes

If $p=2q +1$ with $p,q$ prime then $p$ is called safe prime and $q$ is a Sophie Germain prime. I want a faster algorithm for a safe prime test than doing two primality checks for $p$ and $q$. In ...
2
votes
1answer
81 views

Prime number upper bound

I am reading some written notes about a proof I do not understand, maybe some informations are missing. The result that has to be proved is the following: if $p_n$ is the $n$-th prime number, ...
6
votes
1answer
212 views

Is $7^{8}+8^{9}+9^{7}+1$ a prime? (no computer usage allowed)

Prove or disprove that $$7^{8}+8^{9}+9^{7}+1$$ is a prime number, without using a computer. I tried to transform $n^{n+1}+(n+1)^{n+2}+(n+2)^{n}+1$, unsuccessfully, no useful conclusion.
0
votes
1answer
183 views

Why elements of the set can be Goldbach pairs for a given even number?

Let's take even number $100$ as an example (an example in the paper): Fom $2$ to $\sqrt{100}$ there's four primes:$\ 2,\ 3,\ 5,\ 7.\ $Let $$ \begin{align*} &A=\{n: n \in \mathbb{Z^+}, ...
3
votes
2answers
111 views

$n^2-79n+1601$ always a prime?

I am struggling with proving or disproving this: $n^2-79n+1601$ is a prime for all natural numbers $n$ (except multiples of $1601$). This somehow has a relation to Stanislaw Ulam spiral. What ...
0
votes
0answers
91 views

Arithmetic progression and average of two prime numbers

Let $A=(a_n : n \in \mathbb{N})$ be the sequence given by: $$ \ a_n = a_1 + (n - 1)d,\quad a_1,\ d,\ n \in \mathbb N,\quad d\gt a_1,\quad \gcd(a_1,\ d)=1. $$ For all terms of $A$ greater than $\ ...
2
votes
1answer
73 views

Infinite families of prime numbers

What interesting/useful infinite families of prime numbers are there? Right now it would be useful if I could find one with arbitrarily many 1's in its binary representation, but I am doing a larger ...
0
votes
1answer
37 views

An Inequality Involving Prime Numbers

Let $p_i$ be the $i^{th}$ prime number. It seems as though the following inequality is true for all positive integers $m$ and real numbers $x>1$: ...
0
votes
2answers
48 views

Question regardles primes and the fundamental theorem of arithmetic

I have been reading through my book of practice proofs and came across this particular question which has stumped me. $p$ and $q$ are primes. Prove $\forall p \in \mathbb{Z}, \forall k \in ...
7
votes
5answers
665 views

Induction hypothesis misunderstanding and the fundamental theorem of arithmetic.

The fundamental theorem of arithmetic is made of two parts: The existence part: There exist primes such that for any natural number $j$, we can write $j$ as a product of prime numbers. The ...
2
votes
0answers
81 views

Questions about central polygonal numbers $1, 2, 4, 7, 11, 16, 22, 29, 37, 46,\cdots$

Formula for Central polygonal numbers is $\frac{n(n+1)}{2} + 1$, if $n=1$ or $n$ is prime, we get the new sequence $A$: 2, 4, 7, 16, 29, 67, 92, 154, 191, ... It seems that all primes either is ...
3
votes
1answer
42 views

Can a Mersenne number be a power (with exponent > 1) of a prime?

Let $n \geq 1$ and consider the (Mersenne) number $M_n = 2^n-1$. Is it possible that $M_n = p^k$ for some prime $p$ and some (necessarily odd) $k > 1$? Thanks in advance.
2
votes
1answer
30 views

Extrema of the Ratio of Consecutive Primes

Let $p_i$ denote the $i$th prime number. We know that $\frac{p_{n+1}}{p_n}\rightarrow 1$ as $n\rightarrow\infty$. Therefore, if we pick some real number $c>1$, there should be some positive integer ...
1
vote
1answer
42 views

(p-1)! number theory problem

I was working on this little problem: Let $\frac{a}{(p-1)!} = 1 + 1/2 + 1/3 + ... + 1/(p-1)$, where p is a positive prime. (a) Prove $p\mid a$. (b) Can $p^2 \mid a$? I thought (a) was pretty ...
5
votes
1answer
178 views

Why all composite numbers have this property?

Define $f(n)=\sum\limits_{A \in S} f_{1}(n,A),\ n>2,\ n \in \mathbb{Z}$, where $S$ is the power set of $\{\frac{1}{2},\cdots ,\frac{1}{n-1}\}$. Define $\ f_1(n,\varnothing)=1,\ ...
5
votes
5answers
769 views

Proof of infinitely many primes, clarification

Proof: The proof is by contradiction. Suppose there are only finitely many primes. Let the complete list be $p_1,p_2,\dots,p_n$. Let $N = p_1p_2 \dots p_n+1$. According to the Fundamental Theorem of ...
6
votes
3answers
272 views

Conjecture: If $ N $ and $ N + 10 $ are prime, then $ N + 20 $ is composite.

Conjecture: If $ N $ and $ N + 10 $ are prime, then $ N + 20 $ is composite. Here are some examples: $ 19 $ and $ 29 $ are prime; $ 39 $ is composite. $ 241 $ and $ 251 $ are prime; $ 261 $ is ...
5
votes
7answers
222 views

Alternative Proof of Infinitely Many Primes? [duplicate]

I've seen Euclid's proof of infinitely many primes, what are other approaches to proving there are infinitely many primes?
1
vote
1answer
38 views

Euler totient of a number

If $n= \prod_{i=1}^{m} p_i$, all $p_i$ pairwise distinct, then number of coprimes below $n$ is $\prod_{i=1}^{m} (p_i-1)$. For example with $m=2$, there are $p_2-1$ multiples of $p_1$ below $n$ and ...
0
votes
1answer
56 views

Under assumption that $\frac{M_{n+1}}{M_n} \le 2$, what is true?

This question was hinted upon with the still open question at [1]. Let $M_n = $ A005250($n$) of the OEIS. That is to say, $M_n = p_{i+1}-p_i$, where $p_i$ is the smallest prime such that $p_{i+1} - ...
5
votes
1answer
115 views

Prove that $512^3 + 675^3 + 720^3$ is a composite number

We have to prove that the number $$N=512^3 + 675^3 + 720^3$$ is composite. I tried to use the identity $(a^3+b^3+c^3)=(a+b+c)(a^2+b^2+c^2-ab-bc-ca)+3abc$ hoping to take out some common ...
3
votes
1answer
67 views

1-to-1 correspondence between twin primes and $n^2-1$

I am trying to establish the one-to-one correspondence of twin primes to integers $n$ where $n^2-1$ has 4 divisors. It is clear to me that this is the case, since $$n^2-1=(n+1)(n-1)$$ where the RHS ...
1
vote
1answer
29 views

Any simpler way to do Pollard's p-1 method?

I found calculating factorization by Pollard's p-1 method is almost impossible if use a conventional scientific calculator. For example, I am trying to factor ...
2
votes
1answer
64 views

Proof that there are infinitely many primes of the form $6k+1$. Proof verification

Theorem. there are infinitely many primes of the form $6k+1$. I've just proved that there are infinitely many primes of the form $6k+1$. Could you please check my proof? At first, I proved that ...
1
vote
1answer
33 views

Divisibility of sum of exponents

Consider the sequence $$r, \ ra, \ ra^2, \ ra^3, ... \ , ra^n \mod M $$ such that: $$ ra^{n+1} \equiv r \mod M$$ and $a \ne 1$ and $a,r$ are both coprime to $M$ Is it always true then that: ...
6
votes
3answers
129 views

Primes as a difference of powers

Find the smallest prime that cannot be written as $$|3^a - 2^b|$$ EDIT: I forgot to mention that $a$ and $b$ are whole numbers. I tried to expand $3^a$ as $(2+1)^a$ using binomial theorem but ...
2
votes
3answers
57 views

How to use Legendre symbol to find a prime which divides $ax^2+b$?

I'm trying to prove that $\dfrac{x^2-2}{2y^2+3}$is never an integer if $x,y\in\mathbb{Z}$. It can be proven if $\forall p\in\mathbb{P}\:$doesn't suffice both of the following congruences: $$\: ...
2
votes
2answers
102 views

Prove that $a^n+b^n \equiv (a+b)^n \mod n$, if $n$ is prime and $a,b$ are integers.

What is the best method to prove that if $n$ is prime and $a,b$ are integers $a^n+b^n \equiv (a+b)^n \mod n$, ?
9
votes
5answers
212 views

Are numbers of the form $n^2+n+17$ always prime

Someone claimed that a number, multiplied by the number after it plus 17 is always prime, and showed several cases. I'm not a complete amateur in Number Theory, and I know that $17*18+17=17*19$, so it ...
4
votes
1answer
63 views

Question about the proportions of primes p for which $ord_p(2)$ satisfies certain congruences

let $p$ be a prime. I have observed numerically that the proportion of $p$ satisfying $ord_p(2)\equiv4[8]$ seems to be $1/3$. Why is it so? Is there a simple proof? Moreover the proportion $c$ of ...
0
votes
1answer
71 views

Why does the number of divisors of a superior highly composite number is always a highly composite number up to 720720 ? (the only exception is 120)

I've calculated the number of divisors of every superior highly composite number up to $10^{27}$: http://oi59.tinypic.com/ndaijo.jpg The number of divisors of a superior highly composite number is ...
1
vote
1answer
126 views

Why isn't $1$ a superior highly composite number?

A superior highly composite number is a positive integer $n$ for which there is an $\epsilon>0$ such that $\dfrac{d(n)}{n^\epsilon} \geq \dfrac{d(k)}{k^\epsilon}$ for all $k>1$, where the ...
12
votes
3answers
394 views

Number Theory or Algebra?

Prove that if $4^m-2^m+1$ is a prime number, then all the prime divisors of $m$ are smaller than $5$ I initially thought about putting $4^m-2^m+1=p$ where $p$ is some prime and after eliminating ...
0
votes
1answer
28 views

$\psi(p_{n+1}) - \psi(p_n)$?

Let $$S(p_n)=\psi(p_{n+1}) - \psi(p_n)$$ where $p_n$ is the $n$-th prime, and $\psi(x)$ second Chebyshev function. With $u=\log(x)/\log(2)$, This the same as, with the first Chebyshev function ...
1
vote
0answers
28 views

Is there a Poulet number with this condition?

Is there a Poulet number $n$ with this condition: $◎(n)=\frac{n+1}{2^x}$ or $\ ◎(n)=\frac{n-1}{2^x}, \ x \in \mathbb{N}_{\gt 0}$? (Recall that a Poulet number is a composite $n$ such that $2^n−2$ is ...
0
votes
0answers
48 views

For all prime $\ p > \ 2,\ p=2^x \cdot Ord_p(2)+1$?

For all prime $\ p\ > \ 2,\ p=2^x \cdot Ord_p(2)+1?\ $ Where $\ x \in \mathbb{Z}_{\geq 0}.\ $ Such as $\ Ord_3 (2) = 2, \ 3=2^0 \cdot 2 + 1$. Is there some way to prove this?
1
vote
2answers
70 views

Is it sufficient for a number to be a prime if it is not divisible by prime numbers smaller than it?

I am student of computer science with no knowledge of maths. To write a small algorithm I searched for the solution first. There are many but almost all of them state that continue dividing the number ...
3
votes
1answer
66 views

Existence of a prime partition

I'm interested in finding out whether there exists a prime partition of a given positive integer $N>1$ such that the partition has specific number of parts. For instance, as given in another ...
3
votes
2answers
51 views

$\pi(x)\leq \frac x{f(x)}$ for some unbounded function $f(x)$

Let $\pi(x)$ denote the number of primes $\le x$. Can one prove $$\pi(x)\leq \frac x{f(x)}$$ for some function $f(x)(x\gt0)$, and $f(x)$ is unbounded? Please do not refer to prime number ...
0
votes
0answers
67 views

Among the superior highly composite numbers, which are the most divisor dense numbers?

I’m searching for the most divisor dense natural numbers. Firstly we have the highly composite numbers: 1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, … But ...
5
votes
1answer
68 views

Sum of Residues Modulo $p^2$.

Let $p$ be an odd prime. Prove that $$ \sum_{k = 1}^{p-1} k^{2p-1} \equiv \frac{p(p+1)}2 \pmod{p^2}$$
0
votes
3answers
72 views

Find primes $p_1,p_2,..,p_6$ such that $1+\prod_{i=1}^{6}p_i $is not prime

Show that if$$ p_1, p_2, p_3, p_4, p_5, p_6 $$are primes, then $$1+\prod_{i=1}^{6}p_i$$ is not necessarily prime by using a specic example.
1
vote
1answer
22 views

Finding the Best Constant in Prime Counting Function Relation

How close can we approximate the best constant $c$ such that $n^{\pi(2n)- \pi(n)} \le c^n$ for all positive integers $n$. I know that $c = 4$ works from $n^{\pi(2n)-\pi(n)} < \prod_{n < p \le ...
3
votes
0answers
152 views

Conjecture on OEIS A167055

OEIS A167055 Numbers n such that $12n + 5$ is prime. $0, 1, 2, 3, 4, 7, 8, 9, 11, 12, 14, 16, 19, 21,...$ are items of OEIS A167055. I conjecture that the set of the sum of every two items of this ...
4
votes
3answers
139 views

Tell whether $\dfrac{10^{91}-1}{9}$ is prime or not?

I really have no idea how to start. The only theorem considering prime numbers I know of is Fermat's little theorem and maybe its related with binomial theorem. Any help will be appreciated.
1
vote
0answers
44 views

About a paper by Gold & Tucker (characterizing twin primes)

I've carefully looked at the questions on prime and twin prime, but the following question seems not to habe been asked before. Context: In the paper by Jeffrey F. Gold and Don H. Tucker titled A ...
1
vote
3answers
33 views

Why is $a^c-1$ composite if $a>2$ or if $c$ is composite?

Here is the original theorem from my book (A Course in Number Theory by H.E.Rose, 2nd edition): Let $a>1$ and $c>1$ be integers. The integer $a^c-1$ is composite if $a>2$ or if $c$ is ...
4
votes
1answer
59 views

Primes in an Infinite Set

Let $S$ be the infinite set of positive integers whose members can be written with no digits except $0$ and $1$ and with no more than $1988$ $1s$. Show that some integer $n$ does not divide any member ...