All Questions
Tagged with prime-factorization divisibility
20
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
6
votes
2
answers
678
views
Prove $a^3\mid b^2 \Rightarrow a\mid b$
I think it's true, because I can't see counterexamples.
Here's a proof that I am not sure of:
Let $p_1,p_2,\ldots, p_n$ be the prime factors of $a$ or $b$
\begin{eqnarray}
a&=& p_1^{\...
- 75
16
votes
2
answers
16k
views
Prime factors + number of Divisors
I know that one way to find the number of divisors is to find the prime factors of that number and add one to all of the powers and then multiply them together so for example
$$555 = 3^1 \cdot 5^1 \...
- 263
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
5
answers
14k
views
Proving gcd($a,b$)lcm($a,b$) = $|ab|$
Let $a$ and $b$ be two integers. Prove that $$ dm = \left|ab\right| ,$$ where $d = \gcd\left(a,b\right)$ and $m = \operatorname{lcm}\left(a,b\right)$.
So I went about by saying that $a = p_1p_2......
- 2,148
1
vote
0
answers
433
views
If $n \mid a^2 $, what is the largest $m$ for which $m \mid a$?
Given $n$, what is the largest $m$
such that $m \mid a$ for all $a$ with $n \mid a^2$?
This is a generalization of
if $40|a^2$ prove that $20|a$ when $a$ is an integer
where $n=40$
and $m=20$.
Here ...
- 108k
8
votes
5
answers
1k
views
Shorter proof of irrationality of $\sqrt{2}$?
Euclid's proof of the irrationality of $\sqrt{2}$ via contradiction involves arguments about evenness or odness of $a^2 = 2 b^2$ which is then lead to contradiction in using few more steps. I wonder ...
- 1,715
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
12
votes
3
answers
462
views
On the diophantine equation $x^{m-1}(x+1)=y^{n-1}(y+1)$ with $x>y$, over integers greater or equal than two
I don't know if the following diophantine equation (problem) is in the literature. We consider the diophantine equation $$x^{m-1}(x+1)=y^{n-1}(y+1)\tag{1}$$ over integers $x\geq 2$ and $y\geq 2$ with $...
6
votes
2
answers
558
views
What is sum of totatives of n(natural numbers $ \lt n$ coprime to $n$ )?
Same question as in title:
What is sum of natural numbers that are coprime to $n$ and are $ \lt n$ ?
I know how to count number of them using Euler's function, but how to calculate sum?
- 287
5
votes
2
answers
480
views
Expected number of digits of the smallest prime factor of $1270000^{16384}+1$
The number $N\ :=\ 1270000^{16384}+1$ with $100,005$ digits is given.
Given, that $N$ is composite and does not have a prime factor below $2\times 10^{13}$, what is the expected number of digits of ...
- 85.1k
1
vote
2
answers
60
views
How to proof $a = \left\lfloor\frac{Log(N)}{Log(P)}\right\rfloor$ is the maximum exponent of prime P such that $P^a \le N$
I'm trying to solve Project Euler's Problem #5 which is:
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to N?
I came across a solution here using prime ...
0
votes
1
answer
125
views
Prime divisibility in a prime square bandtwidth
I am seeking your support for proving (or fail) formally the following homework:
Let $p_j\in\Bbb P$ a prime, then any $q\in\Bbb N$ within the interval $p_j<q<p_j^2$ is prime, if and only if all:...
- 4,310
11
votes
3
answers
537
views
Show that $(n!)^{(n-1)!}$ divides $(n!)!$ [duplicate]
Show that $(n!)^{(n-1)!}$ divides $(n!)!$
I found this question in a text he was reading about BREAKDOWN OF PRIME FACTORS IN FACT, I decided many years, have posted some here to help, but this ... ...
- 3,789
4
votes
3
answers
393
views
If $a \mid c$ and $b \mid c$, but $\gcd(a,b) = 1$, then $ab \mid c$.
If $a | c$ and $b | c$ and $a$ and $b$ are relatively prime prove that
$ab|c$.
What I did was since $(a,b)=1$ then we can find integers $m,n$ such that $ma + nb=1$. Now since $a|c$ then $a = mc$. ...
- 1,089