Tagged Questions
1
vote
2answers
56 views
If $2n+1$ and $4n+3$ are prime, then $2n-1$ and $4n+1$ are not when $n>2$
How do you prove that, for $n>2$, if $2n+1$ and $4n+3$ are prime numbers, then $2n-1$ and $4n+1$ are composite numbers?
2
votes
0answers
34 views
Only 3 $n$ where $q=\left\lfloor (2 p_n+p_{n+2}) (p_{n}+p_{n+1}+p_{n+2})\over p_{n}\right\rfloor,\;\text{isPrime}(q)$?
Consider: $$q=\left\lfloor (2 p_n+p_{n+2}) (p_{n}+p_{n+1}+p_{n+2})\over p_{n}\right\rfloor,\;\text{isPrime}(q)$$
where $p_n$ denotes the $n$th prime.
Other than: $$n=6\quad\text{or}\quad ...
2
votes
1answer
57 views
Is this elementary number theory proof correct?
Let $A(n)$ be the number of primes less than $n$, divided by $n$ (so for example, $A(n) \leq 1$, as there cannot be more primes less than $n$ as there are integers less than $n$). Suppose that $n$ is ...
5
votes
2answers
101 views
Do there exist $29$ consecutive integers so that every of them has exactly $2$ distinct prime factors?
Do there exist $29$ consecutive integers, denote $a,a+1,\cdots,a+28$, so that every of them has exactly $2$ distinct prime factors?
For example, $25$ has only one distinct prime factor, and $30$ ...
3
votes
1answer
68 views
Why is $n=\frac{2p^2+2pq+2pr+q^2+2qr+r^2}{p+q+r}$, where $n$ is $\text{prime}$, of form such that $p\pm a,p\pm b,$ are $ \text{prime}, 1<a<b<n$
Why is $n= \left\lfloor \frac{2p^2+2pq+2pr+q^2+2qr+r^2}{p+q+r} \right\rfloor$, where $n$ is $\text{prime}$, of form such that $p\pm a,p\pm b,$ are $ \text{prime}, 1<a<b<n$?
Consider this:
...
0
votes
1answer
41 views
Why is $\{n=4r+1,r = {n-1\over 2}\}\subset \mathbb{P}$ true under these conditions?
Let $p=p_k$, $q=p_{k+1}$ and $r=p_{k+2}$, where $p_m$ denotes the $m$th prime.
I conjecture that whenever $n$ is prime, where $n$ is defined as follows:
$$n = 1+\left(\left\lfloor{p\over ...
1
vote
2answers
40 views
Proving x and y is divisible by p (prime).
If p is a prime number and x and y are integers, how do I prove "if xy and x+y are both divisible by p, then x and y is divisible by p"?
I started like this..
1) p divides xy, so p divides x or p ...
2
votes
0answers
114 views
primes of the form $p=8k+1, 8k+3$ can be expressed as $p=a^2+2b^2$
I have trouble showing that primes of the form $p=8k+1, 8k+3$ can be expressed as $p=a^2+2b^2$.
Thanks in advance.
1
vote
0answers
34 views
Revised: Primes of form $p \equiv m \in S \mod x \ $
Refer to this question for background.
I was speculating if there was an elegant way to define sequences
A007645,A002313,A045357,A045407,A042986,A045331,
A045425,A045374,A045400,A045350,A042988;
...
3
votes
3answers
42 views
Infinitely many primes of the form $4n+3$
I've found at least 3 other posts$^*$ regarding this theorem, but the posts don't address the issues that I have.
Below is a proof that for infinitely many primes of the form $4n+3$, there's a few ...
1
vote
1answer
48 views
Regarding definition of cuban primes
While considering the relationship between $6n-1$ (OEIS A002476) and generalized cuban primes(OEIS A007645) I came across something I thought was interesting:
Seems like the description of ...
1
vote
2answers
42 views
Classify the odd primes $q$ such that a NEGATIVE number is a quadratic residue $\mod{q}$
Suppose we are given $y < -1$. I wish to classify all primes $q$ such that $y$ is a quadratic residue $\pmod{q}$, i.e. such that there exists a number $x$ satisfying $$y \equiv x^2 \pmod{q}.$$
How ...
2
votes
1answer
49 views
Finding a prime $p$ to solve a quadratic congruence $\pmod{p}$
I have a congruence of the form $$ax^2+bx \equiv -1 \pmod{p},$$
where $p$ is an odd prime and $a,b \in \mathbb{Z}$. Given $a$ and $b$, is there a general method to finding $p$ such that the above ...
3
votes
1answer
49 views
$\sigma(\sigma(p^2)) \neq 2p^2$ for all odd primes $p$.
How to prove that $\sigma(\sigma(p^2)) \neq 2p^2$ for all odd primes $p$?
I know that $\sigma(p^2)=1+p+p^2$ but I can't progress anymore.
2
votes
1answer
49 views
The set of exponential primes
Consider a set of integers $Q$ such that the set of all positive integers $\mathbb{Z}$ is equivalent to the span of ever possible power tower
$$a_1^{a_2^{\ldots a_N}}$$ involving $a_i \in Q$.
In ...
2
votes
1answer
43 views
Sequence of primes.
This is a previous year question and I have no idea how to start.
Let $p_1<p_2<....<p_{31}$ be prime numbers such that $30$ divides $\sum_{i=1}^{31}p_i^4$.
Prove that $p_1=2, ~p_2=3 , ...
1
vote
1answer
63 views
Proof regarding prime numbers:
THEOREM:
If a prime $p$ divides a product $a_1 \cdot \cdot \cdot a_n$, then $p$ divides at least one of its factors, $a_i$.
This is my attempt at the proof, the book I am reading from suggests ...
14
votes
3answers
323 views
An Elementary Number theory Problem
A mathematician friend gave me this question (partly as a joke) a few months ago and it has puzzled me for a long time:-
Do there exist infinitely many pairs of primes $(p,q)$ such that ...
9
votes
1answer
194 views
Can the order of 2 mod p be arbitrarily small (relative to $p - 1$)?
Given a prime number $p$, let $\operatorname{ord}_p(2)$ be the multiplicative order of $2$ modulo $p$, i.e., the smallest integer $k$ such that $p$ divides $2^k - 1$. By Lagrange's theorem, ...
8
votes
3answers
156 views
Number theory: Prime powers and cubes
Determine all triples $(p,a,b)$ of positive integers, where $p$ is prime and $a \leq b$ such that $$p^a+p^b$$ is a perfect cube.
I came across this question while looking at past maths Olympiad ...
9
votes
6answers
670 views
Prove $a+b+c+d $ is composite
Let $a,b,c,d$ be natural numbers so that $ab=cd$.
Prove that $a+b+c+d$ is composite.
1
vote
1answer
64 views
Average of divisors of n.
Let n be a natural number and let $f(n)=\frac{\sigma(n)}{d(n)}$ be the arithmetical average of n's divisors. Either prove or give a counterexample that for all natural numbers like n, which are not ...
3
votes
2answers
77 views
Prove by mathematical induction for any prime number$ p > 3, p^2 - 1$ is divisible by $3$?
Prove by mathematical induction for any prime number $p > 3, p^2 - 1$ is divisible by $3$?
Actually the above expression is divisible by $3,4,6,8,12$ and $24$.
I have proved the divisibility by ...
4
votes
1answer
60 views
Constraints on $x$ such that $2x+1$ is prime
I have read quite a bit about prime numbers recently (having just started a module on elementary number theory, groups, primes, etc.), and something that always seems to be popping up is powers of 2. ...
27
votes
5answers
3k views
Are all prime numbers finite?
If we answer false, then there must be an infinite prime number. But infinity is not a number and we have a contradiction. If we answer true, then there must be a greatest prime number. But Euclid ...
1
vote
0answers
62 views
Fourier Analysis of Prime Counting Function
I was thinking about the following:
Denote $\pi(x)$ as the prime counting function such that:
$$
\pi(x) = \#\text{ of prime numbers}\leq x
$$
It is well known from the prime number theorem that
$$
...
1
vote
1answer
91 views
Prove or disprove: There exists an integer $k\geq 4$ such that $2k^2 -5k+2$ is a prime number
Prove or disprove: There exists an integer $k\geq 4$ such that $2k^2 -5k+2$ is a prime number.
If true (which I'm pretty sure it isn't), then the proof needs to be in either contradiction or ...
1
vote
1answer
53 views
Does $a \mid bc$ imply $\frac{a}{(a,b)} \mid c$?
If $a \mid bc$, then does $\frac{a}{(a,b)} \mid c$? I doubt anybody here is industrious enough to show this via a diagram, but who knows.
1
vote
3answers
82 views
Prime number characterisation using congruences
I want to prove that $n$ is prime. From the Wilson's theorem it follows that $n$ is prime if and only if
$$(n-1)! + 1 \equiv 0 \pmod{n}$$
However, in my proof, I reduce the congruences to the ...
-1
votes
2answers
125 views
How to fast check if a number is a prime number? [closed]
Let say I've found a very very very long prime number. I know it's prime but I need to have a proof. Is there any fast way how to check if a number is really prime?
Let say I've found the longest ...
3
votes
1answer
103 views
Is my proof correct? $p_1p_2p_3\cdots p_n+1)$ cannot be the square of an integer
Prove that $p_1p_2p_3\cdots p_n+1$, where $p_n$ is the $n^{th}$ prime, cannot be the square of an integer.
Let $p_1p_2p_3\cdots p_n+1=Q$ and assume it is the square of an integer, so ...
2
votes
2answers
49 views
About linear combinations of primes
$a,b,c$ are natural numbers whose greatest common divisor is $1$.
$a,b,c\in\mathbb{N}^*$, $(a,b,c)=1$
Try to write down the expression using $a,b,c$ of the biggest natural number $M$ that cannot be ...
3
votes
1answer
77 views
Using Fermats Little Theorem to show $2^{17} -1$ is prime
Show that $n = 2^{17} - 1$ is prime by using Fermat's Little Theorem $2^{p-1} \equiv 1 \mod p$ for any $p$ dividing $n$.
I said, that by FLT, we get $2^{16} \equiv 1 \mod 17$, and we can see that ...
4
votes
4answers
143 views
Is every prime number the leg of exactly one right triangle with integer sides? What's wrong with my argument that this is impossible?
The problem is: "prove that every prime number is the leg of exactly one right triangle with integer sides." However, I seem to have proved that this is impossible. What did I do wrong here?
Let ...
3
votes
4answers
83 views
Formulae for both identifying or generating primes; Shows arranged distribution. Solved; basically trial division.
While looking at numbers and considering $n < p < 2n - 2$ and $p = 3n\pm 1$, where $p$ is any prime number, I was able identify a property for numbers $c=3n\pm 1$ where $c$ is a composite ...
4
votes
2answers
61 views
$(p-2)!-1 \neq p^k$ for any $k\in \mathbb{N}$, $p$ is a prime.
$(p-2)!-1 \neq p^k$ for any $k\in \mathbb{N}$, $p>5$, $p$ is a prime.
How to solve this?
2
votes
1answer
55 views
Prove the converse of Wilson's Theorem
... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime.
This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it ...
4
votes
4answers
147 views
Why 4 is not a primitive root modulo p for any prime p?
I wonder why 4 is not a primitive root for any prime p ?
I've been trying to find an answer with no success so far. Any suggestion would be very helpful,
thanks in advance !
4
votes
3answers
133 views
Show that there exists $f ∈ \mathbb{Z}$ such that $f^2 + f +1 ≡ 0 \pmod p$.
Let $p ≡ 1 \pmod 3$ be a prime. Show that there exists $f \in \mathbb{Z}$ such that $f^2 + f +1 \equiv 0 \pmod p$.
I know the first few primes of this form are: $7,13,19$
So for example $p=7$ we ...
31
votes
6answers
2k views
Is $2^{218!} +1$ prime?
Prove that $2^{218!} +1$ is not prime.
I can prove that the last digit of this number is $7$, and that's all.
Thank you.
5
votes
2answers
101 views
Very interesting Number Theory problem
Let $a>3$ be an odd integer. Prove that for every positive integer $n$, the number $a^{(2^{n})}-1$ has at least $n+1$ distinct prime divisors.
This problem smells very strongly of induction, but ...
3
votes
4answers
73 views
How to derive this expression $ r ^{ (p-1)/2} \equiv -1 \pmod p$ for primitive root of an odd prime $p$.
While studying Elementary Number theory by David M. Burton I came across this line:
because $r$ is a primitive root of $p$, $$ r ^{ (p-1)/2} \equiv -1 (\mod p) $$ where $p$ is an odd prime.
...
8
votes
0answers
215 views
Understanding Ramanujan's approach in his proof of Bertrand's Postulate
I've been reading through Ramanujan's proof of Betrand's Postulate and I'm not clear why he didn't state his proof in terms of $\varphi(2x) - \varphi(x)$
What would be wrong with this approach for ...
1
vote
2answers
51 views
Number of proper divisors generally prime
If we count the number of proper divisors of a positive integer, why do we usually get a prime number (or $1$)?
...
1
vote
1answer
41 views
Missing one link in logic of basic unique factorization argument
From page 2 of The Prime Facts : from Euclid to AKS by Scott Aaronson :
Thus P/A = R/K. But R is less than P, since it’s a remainder from dividing by P.
Okay
So P/A can’t be in lowest ...
0
votes
1answer
29 views
Finding the remainder of $x^{y^z}\pmod k$ if $k$ is prime.
I am trying to find the remainder of $x^{y^z}\pmod{k}$ if $k$ is prime.
I am trying to use little Fermat theorems but I cannot really generalize the $x,y,z$. I need an general algorithm to automate ...
1
vote
1answer
68 views
A new primality test for Proth primes?
Here is what I have observed. $p = k2^n+1$ (a Proth number), $k$ is odd,
If $x^2+1$ mod p=0, has 2 solutions x=+- r mod p , then p is prime,
If $x^2+1$ mod p=0,has more than 2 solutions or no ...
1
vote
1answer
51 views
Erdős–Turan construction of Golomb ruler
The following equation produces a Golomb ruler for every odd prime p
$$ 2pk + (k^2 \bmod p), \quad k\in[0,p-1] $$
and every two contiguous points has a unique difference.
my question is how to get ...
5
votes
1answer
179 views
Prove ${a^2+ac-c^2=b^2+bd-d^2}$ and $a > b > c > d \implies ab + cd$ is not prime
Let $a>b>c>d$ be positive integers and suppose that
$${a^2+ac-c^2=b^2+bd-d^2}$$
Prove that $ab+cd$ is not prime? I don't know if this problem is true.
I found that this same problem has ...
5
votes
1answer
102 views
Super prime numbers
I was reading about super prime numbers in Wikipedia, nothing looks Unusual until i read this line.
every integer greater than 96 may be represented as a sum of distinct super-prime numbers.
i ...
