0
votes
1answer
43 views

Prime factorization of 2^(16) - 1

Trying to show the the prime factorization of $$2^{16}-1$$ without a calculator. I know that $2^{16} - 1$ yields the prime numbers$$3*5*17*257$$ because I calculated $2^{16}-1$ on my calculator ...
0
votes
4answers
29 views

Let $p \geq 5$ and prime. Show $p^2 + 2$ is divisible by three.

I know I have to use the division algorithm to put into the form $p^2 + 2 = 3q + r$ but everything I've tried after that has lead me to a dead end. I've mainly been trying to show $r=0$ or to make the ...
2
votes
1answer
41 views

Divergence of a series containing primes

Is there an easy proof showing that the series $1/p$, where $p$ changes over prime numbers, is divergent?
2
votes
1answer
32 views

p-adic numbers and GCD

Given two numbers $a,b \in \mathbb{Z}$, how do we prove that the $p$-adic number of $\gcd(a,b)$ is the same as the minimum for the $p$-adic number of $a$ and the $p$-adic number of $b$? Does this ...
3
votes
1answer
48 views

Foundational proof for Mersenne primes

I know how to prove that, if $2^n-1$ is prime and $n>1$, then $n$ is prime. But how do we prove that, if $a^n-1$ is prime and $n>1$, then $a$ must equal 2?
0
votes
0answers
24 views

Fermat number factor probability

I found a question I couldn't solve: What is the probability that $2^{2^{12}}+1$ has a prime factor of $70$ digits? I found this problem hard as many number has more small prime factors than large ...
0
votes
1answer
40 views

Asymptotic sum of the squares of the first n primes [closed]

I know there is an asymptotic formula for the sum of the squares of the first n primes, but I have been unable to find it.
0
votes
0answers
19 views

Could you give a definition of what is a superior highly composite number using only words?

I know very well what is a superior highly composite number, but I would like to see how could we (roughly) define what is a superior highly composite number using only words (using no equations and ...
2
votes
1answer
109 views

Between $n$ and $2n$ there is always a prime number. [duplicate]

Between $n$ and $2n$ there is always a prime number. I was thinking of this and looked it up on the google to find that this is true. Now, I am wondering what is the proof for it? Does any ...
1
vote
5answers
70 views

prove if a|b and b|a then $a = \pm b$

Fairly basic I guess. Attempt: $a\neq\pm b \Rightarrow a\nmid b \vee b \nmid a$ let $a = \pm b + d, d\in \mathrm{Z} \wedge d\neq 0$ then $a\mid b \Rightarrow b\nmid a$ and $b\mid a \Rightarrow ...
38
votes
2answers
2k views

Does the string of prime numbers contain all natural numbers?

Does the string of prime numbers $$2357111317\ldots$$ contain every natural number as its sub-string?
2
votes
1answer
45 views

The perimeter of triangle $ABC$ where $|BC|=293$, $|AB|$ is a square, $|AC|$ is a power of $2$, and $|AC|=2|AB|$

In triangle $ABC$ length of side $BC$ is $293$ (a prime). If length of side $AB$ is a perfect square, length of side $AC$ power of 2 and $AC$ twice length of $AB$, find the perimeter. Kind of ...
3
votes
2answers
282 views

A number is a perfect square if and only if it has odd number of positive divisors

I believe I have the solution to this problem but post it anyway to get feedback and alternate solutions/angles for it. For all $n \in \mathrm {Z_+}$ prove $n$ is a perfect square if and only if $n$ ...
0
votes
0answers
39 views

Explanation of a proof of the existence of reclusive primes

The goal is to prove: For any given number $N$, there exists a prime number that is at least $N$ greater than the previous prime number and at least $N$ smaller than the following one. We call those ...
10
votes
5answers
2k views

Disproving the claim that the numbers 1+2+4, 1+2+4+8, 1+2+4+8+16… alternate between prime and composite

I am working through an elementary number theory book and I have come across the following problem. Show the following claims are wrong: Claim 1: The sequence 1+2+4, 1+2+4+8, 1+2+4+8+16, ...
1
vote
1answer
66 views

prime division problem

$a,b,c \in$ {0,1,2,...,9} with at least one of $a,b,c$ nonzero. Prove that the six-digit integer $abcabc$ is divisible by at least 3 distinct primes. My thinking is not to use induction as there is ...
1
vote
2answers
59 views

$2p-2$ as the sum of consecutive prime numbers

Progress: Let $p$ be a prime such that $p≡1$ (mod 6) then $2p-2$ can be written uniquely (up to the order of addends) as the sum of some consecutive prime numbers. These are first ten examples: ...
4
votes
0answers
190 views

Prove modular equivalence related to carmichael function.

Statement if $n=p_1p_2p_3\cdots p_r$ (prime numbers are distinct) and $2 \le a \le n-1$ then prove that $$a^{k\lambda} \equiv \left(1+\sum_{p_i\mid\gcd(a,n)}\left(\dfrac{n}{p_i} \right) ...
0
votes
3answers
104 views

$6n+1$ and $6n-1$ prime format [duplicate]

I recently stumbled upon a fact that all prime numbers past $3$ are of the form either $6n-1$ or $6n+1$. Is it true? at least for numbers less than $10^9$. And does it cover all primes?
0
votes
2answers
65 views

What percent of numbers are primes? [duplicate]

I understand that there are infinitely many primes and (obviously) infinitely many integers, but is there any way to calculate the total percentage of integers that are primes? Thanks
2
votes
2answers
58 views

Diophantine: $px^2+2=y^2$ where $p\in \mathbb{P}$

Solve the Diophantine Equation: $px^2+2=y^2$, where $p$ is a prime number and $x,y$ integers. I tried this for ages but didn't get anywhere, but I don't know any advanced machinery since I am only in ...
0
votes
0answers
45 views

Number of prime factors of Mersenne numbers

Let $p$ be a prime and let $M_p = 2^p-1$. Is it known whether the number of prime factors of $M_p$ is unbounded above as $p \to \infty$? Also do the probabilities estimating the chance that $M_p$ is ...
3
votes
0answers
38 views

Are there infinitely many prime numbers in $a_n=\frac{7\times 10^n-1}{3}$?

In the array $a_n=\frac{7\times 10^n-1}{3}$, are there infinitely many primes? (when $n={7+16k},a_n$ is divisible by $17$, so there are infinitely numbers not prime)
1
vote
4answers
148 views

The fastest way to count prime number that smaller or equal N

I want to count all prime numbers that existing in N but I don't know how to count. Can any one tell me how to count prime numbers that are smaller than or equal to N in mathematics formal?
4
votes
1answer
113 views

Elementary proof there are infinitely many primes of the form $4n+1$

My attempt: $4n+1$ is odd. Thus its decomposition must not contain $2$. Every odd number is either of the form $4k-1$ or $4m+1$. $(4m+1)(4k-1)$ is never of the form $4n+1$. So $4n+1$ has factors ...
-1
votes
2answers
107 views

Why is $y^{x-1}-1$ divisible by $x$?

I wanted to know if there is a way to prove that $y^{x-1}-1$ is divisible by $x$. Where $x$ is a prime number and is not equal to $y$, and $y$ is any positive whole number besides $1$. For example, ...
14
votes
3answers
894 views

Finitely many Supreme Primes?

A challenge on codegolf.stackexchange is to find the highest "supreme" prime: http://codegolf.stackexchange.com/questions/35441/find-the-largest-prime-whose-length-sum-and-product-is-prime A ...
1
vote
2answers
44 views

Can't understand source of constant for prime counting function:

Consider the prime counting function $$ \pi(x) = \ the \ number \ of \ primes \ less \ than \ or \ equal \ to \ x$$ It is well known due to the sieve eratosthenes that given an integer $n$ and the ...
1
vote
3answers
53 views

First index of number in that arithmetic progression which is a multiple of the given prime number

I have a prime number $p$, an arithmetic progression starting at $a$ with common difference $d$. How to find the first index of a term in that arithmetic progression which is a multiple of the given ...
0
votes
1answer
123 views

Primes and the number of digits of the prime [duplicate]

Say $n$ has $k$ decimal digits, all of which are ones. How would you show that if $n$ is prime, then $k$ is prime?
0
votes
1answer
154 views

Let $x = 2441921$. Factor $x$ into a product of primes.

Let $x = 2441921$. Factor $x$ into a product of primes. I found that: $1519^2 −x=−134560= −2^5 ·5 · 29^2$ and $1541^2 −x=−67240= −2^3 · 5 · 41^2$. I am trying to figure out what to do from here. ...
0
votes
2answers
70 views

Represent a prime number $p$ congruent to $1$ $\pmod{3}$ by a sum of a square and $3$ times a square

I want to have a proof of the fact that each prime number is the sum of a square and three times a square (Euler). Context I read the answer to my former question about the number of points on an ...
1
vote
4answers
74 views

$p$ prime, $p\mid a^k \Rightarrow p^k\mid a^k$

Suppose $p$ is a prime and $a$ and $k$ are positive integers. Prove that if $pa^k$ then $p^k\mid a^k$. I have already proven that if $a,b,n\in\mathbb{N}$ and if $a^n\mid b^n$, then $a\mid b$. I tried ...
4
votes
0answers
47 views

Computing question: A quadratic which gives primes [closed]

This is about Project Euler Problem 27. The question is: Considering quadratics of the form $n^2 + an + b$, where $\lvert a \rvert < 1000$ and $\lvert b \rvert < 1000$ Find the product ...
3
votes
2answers
56 views

Prove that every non-prime natural number $ > 1$ can be written in the form of $n+(n+2)+(n+4)+…+(n+2m) = p$

I'm trying to prove that every non-prime natural number greater than $1$ can is equal to a sum of consecutive even or odd numbers. This can be resumed in : « $p,m,n \in ℕ$» , «$p > 1$» , «$n > ...
0
votes
0answers
29 views

Find a criterion for the primes p such that (5/p) = 1. [duplicate]

Find a criterion for the primes p such that (5/p) = 1. I don't understand this question it is like Determine all primes P such that (5/p)=1 I appreciate any help
0
votes
1answer
27 views

Divisibility of $a^p-r$ and $a^q-r$ by the primes $p,q$

Let $p, q$ be prime and $a$ some positive integer such that $a = pq + r$ where $r$ is the remainder. Show that $p \mid a^p – r$ and $q \mid a^q – r$. Example: $p = 3$ and $q = 5$, $a = 17$ and $r = ...
1
vote
1answer
126 views

Andrica's conjecture implies Bertrand's Postulate?

Let $p_n$ denote the $n$th prime. Recall Andrica's conjecture, which states that $$\sqrt{p_{n+1}}-\sqrt{p_n}<1\quad\text{ for all }\,n.$$ I think Andrica's conjecture implies Bertrand's postulate. ...
3
votes
1answer
62 views

If $p$ is prime, prove that $\exists k\in\lbrace 5,-7,9,-11,..\rbrace$ in $(\mathbb{Z}/p\mathbb{Z})^*$ so that the Legendre symbol $(\frac{k}{p})=-1$

The BSPW primality test, when given $p$ as input, iterates over $k \in \lbrace 5,-7,9,-11,...\rbrace$ as long as the Legendre symbol $(\frac{k}{p})=1$. If $(\frac{k}{p})=0$, it returns "composite". So ...
3
votes
0answers
103 views

The n-envelope problem

This is original problem: You have n number of envelopes, and 100 $1 bills. you have to put these bills in the envelopes in such a way that any amount between 1 to 100 can be reached just by ...
3
votes
1answer
106 views

Showing that if $p$ is prime, then $(p^4 + 4)$ can't be prime

I want to show that if $p$ is prime, then $(p^4 + 4)$ can't be prime. I guess Fermat's little theorem may help, but I can't figure out how to use it for the proof. Can anyone point me in the right ...
0
votes
2answers
130 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
114 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
48 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
89 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, ...
7
votes
2answers
271 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
195 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
125 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
102 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
83 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 ...