All Questions
Tagged with prime-factorization elementary-number-theory
92
questions
4
votes
3
answers
508
views
Rings where divisors of $mn$ are product of divisors of $m$ and $n$; relation to UFDs
Using the fundamental theorem of arithmetic, it's easy to prove this proposition:
Proposition. Every divisor of $mn$ can be written as the product of a divisor of $m$ to a divisor of $n$.
My ...
3
votes
4
answers
3k
views
How to use fundamental theorem of arithmetic to conclude that $\gcd(a^k,b^n)=1$ for all $k, n \in$ N whenever $a,b \in$ N with $\gcd(a,b)=1$?
How to use fundamental theorem of arithmetic to conclude that $\gcd(a^k,b^n)=1$ for all $k, n \in$ N whenever $a,b \in$ N with $\gcd(a,b)=1$?
Fundamental theorem of arithmetic: Each number $n\geq 2$ ...
2
votes
4
answers
774
views
Induction in the proof of the existence of prime factorizations
The fundamental theorem of arithmetic states that every positive integer greater than 1 is either a prime or a product of primes.
First question: why "either a prime or a product of primes", if ...
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+...
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
votes
3
answers
3k
views
Suppose that $p$ ≥ $q$ ≥ $5$ are both prime numbers. Prove that 24 divides ($p^2 − q^2$)
I suppose I need to use prime factorization.
I want to show $p^2-q^2=24k$ for some integer $k$ .
How can I start this proof?
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 ...
1
vote
3
answers
953
views
Proof of Euclid's lemma using fundamental theorem of arithmetic
I want a proof of Euclid's theorem (if p is prime and p|(a.b) where a and b are integers, then either p|a or p|b) using the fundamental theorem of arithmetic. I already understand the proof assuming ...
1
vote
2
answers
577
views
What are the integer solutions to $a^{b^2} = b^a$ with $a, b \ge 2$
I saw this in quora.
What are all the
integer solutions to
$a^{b^2} = b^a$
with $a, b \ge 2$?
Solutions I have found so far:
$a = 2^4 = 16, b = 2,
a^{b^2}
= 2^{4\cdot 4}
=2^{16},
b^a = 2^{16}
$.
$...
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 ...
4
votes
3
answers
291
views
Is my intuition of "If $p \mid ab$ then $p \mid a$ or $p \mid b$" correct?
I'm studying number theory and I was given this Theorem to look at:
If $p \mid ab$ then $p \mid a$ or $p \mid b$
I had the following intuition for the problem or a proof of sorts if you will.
...
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."...
11
votes
4
answers
29k
views
Why perfect square has odd number of factors [closed]
can someone please describe me why only the perfect square has odd number of factors.why does other number not has odd numbers of factors? I understand it but don't find any mathmetical proof.Please ...
5
votes
2
answers
4k
views
Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer [duplicate]
Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer
if $n$ is odd then $n=2^{0}n$, but I dont know what to do when $n$...
3
votes
6
answers
158
views
For what integer values of $y$ is $\frac{3y-1}{y-3}$ an integer? [duplicate]
I have encountered this as part of a bigger problem but I really don't know how to go on about it. I would also appreciate it if you could specify a certain technique to follow when facing such a ...