All Questions
Tagged with prime-factorization elementary-number-theory
608
questions
1
vote
1
answer
1k
views
Prime and Factorization, prime divisor property
Let $p$ be prime. Then if $p|ab$ then $p|a$ or $p|b$.
Proof:
Suppose $p$ does not divide $a$
Then $\gcd (a,p) = 1$ since $p$ is prime.
$$ 1 = ma + np $$
$$ b = mab +npb$$
Since $p|map$ and $p|npb$...
- 151
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
2
votes
1
answer
98
views
Fermat's Method - Derive worst case $n=3p$
I am currently trying to understand Fermat's method: for a number $n$ we start with $x=\lceil\sqrt{n}\rceil$ and check if $\sqrt{x^2-n}\in\mathbb N$, if not, increase $x$ and try again, etc. until $x^...
- 23
11
votes
2
answers
3k
views
Factoring a number of complex integers?
Say you are given a number (ex: $377$) and you express it in a form that allows you to factor it over the complex integers:
Notice,
$377 = 16^2 + 11^2$
Thus:
$(16 + 11i) $ and $(16 - 11i)$
Are ...
- 17.5k
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
1
vote
1
answer
98
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.
- 477
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
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$ ...
user2723