All Questions
Tagged with prime-factorization prime-numbers
98
questions
16
votes
6
answers
16k
views
prime divisor of $3n+2$ proof
I have to prove that any number of the form $3n+2$ has a prime factor of the form $3m+2$. Ive started the proof
I tried saying by the division algorithm the prime factor is either the form 3m,3m+1,3m+...
- 2,935
4
votes
4
answers
4k
views
Understanding that there are infinitely many primes of form $4n+3$
I read the proof of, that there are infinitely many primes of form $4n+3$ and it goes here:
Proof. In anticipation of a contradiction, let us assume that there exist only finitely many primes of ...
- 3,381
5
votes
4
answers
3k
views
The square of n+1-th prime is less than the product of the first n primes.
I wanted to prove the following question in an elementary way not using Bertrand postulate or analytic estimates like $x/\log x$. The question is
$$
p_{n+1}^2<p_1p_2\cdots p_n,\qquad(n\geq4)
$$
I ...
- 929
3
votes
2
answers
152
views
Numbers $a$ such that if $a \mid b^2$ then $a \mid b$
I want to describe the set of numbers $a$ such that if $a \mid b^2$ then $a | b$ for all positive integers b using the prime factorizations of $a$ and $b$.
What would be a good way to approach this ...
- 401
8
votes
0
answers
447
views
The Greatest Common Divisor of All Numbers of the Form $n^a-n^b$
For fixed nonnegative integers $a$ and $b$ such that $a>b$, let $$g(a,b):=\underset{n\in\mathbb{Z}}{\gcd}\,\left(n^a-n^b\right)\,.$$ Here, $0^0$ is defined to be $1$. (Technically, we can also ...
- 49.8k
2
votes
0
answers
875
views
Can the sum of two squares be used to determine if a number is square free?
Mathword (http://mathworld.wolfram.com/Squarefree.html) stated that "There is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer."...
- 1,058
2
votes
2
answers
8k
views
Prove that if $p$ and $p^2+2$ are prime then $p^3+2$ is prime too [duplicate]
I'm trying to figure out how to prove that if $p$ and $p^2+2$ are prime numbers then $p^3+2$ is a prime number too.
Can someone help me please?
- 501
0
votes
3
answers
233
views
How can I solve the folowing Diophantine equation with two unknowns?
Find one integer solution to the following Diophantine equation:
\begin{equation*}
\\\forall \,x,y \in \mathbb{Z}\\
6xy + x - y = 274
\end{equation*}
The resultat ist $x = 9$, $y = 5$ (Obtained ...
- 3,919
45
votes
6
answers
1k
views
Can a number be equal to the sum of the squares of its prime divisors?
If $$n=p_1^{a_1}\cdots p_k^{a_k},$$ then define
$$f(n):=p_1^2+\cdots+p_k^2$$
So, $f(n)$ is the sum of the squares of the prime divisors of $n$.
For which natural numbers $n\ge 2$ do we have $f(n)=...
- 85.1k
8
votes
2
answers
6k
views
Upper bound number of distinct prime factors
I want to prove that if $\omega (n)$ is the number of distinct prime factors of $n$ for $n>2$ we have $\omega (n) \leq \frac{\ln n}{\ln \ln n} + O(\frac{\ln n}{(\ln \ln n)^2})$.
How can I do this?
- 291
5
votes
2
answers
349
views
prove that $f_n = 37111111...111$ is never prime [duplicate]
Let $$f_n = 37111111...111$$ with n 1's.
Prove that $$f_n$$ will never be prime for $$n\ge1.$$
I tried to look $$f_n$$ in mod(p), assuming $$f_n$$ is prime, for the sake of contradiction. I also ...
- 111
4
votes
2
answers
196
views
Showing $\sum\limits_{p \in P} \frac{1}{p}$ where $P$ is the set of all primes is divergent
I've been reading proofs of this theorem, and I was wondering why the following is true:
We know that $\sum\limits_{n=1}^{\infty}\frac{1}{n}$ diverges. I'm not sure how knowing this fact leads us to ...
- 6,534
3
votes
2
answers
2k
views
Inverse of prime counting function
The prime counting function $ \pi (x) \approx \dfrac {x} {\ln(x-1)} $.
This function returns the number of primes less than $x$.
Note: $x-1$ gives a better estimate than $x$.
How to find $x$ given $ ...
- 469
3
votes
2
answers
3k
views
Primality test bound: square root of n
I was reading about primality test and at the wikipedia page it said that we just have to test the divisors of $n$ from $2$ to $\sqrt n$, but look at this number:
$$7551935939 = 35099 \cdot 215161$$
...
- 349
2
votes
3
answers
649
views
For which natural numbers are $\phi(n)=2$?
I found this exercise in Beachy and Blair: Abstract algebra:
Find all natural numbers $n$ such that $\varphi(n)=2$, where $\varphi(n)$ means the totient function.
My try:
$\varphi(n)=2$ if $n=3,4,...
- 4,794