Given this theorem: For every prime 𝑝 and all integers a, b, if p|ab, then p|a or p|b Prove: Let 𝑥 ∈ ℤ and 𝑝, 𝑞 be distinct primes. Then p|x and q|x if and only if pq|x I have already proven if p|x and q|x then pq|x. Now I need to prove it the other way around, if pq|x then p|x and q|x I have this: We have pq|x which means x = pqn, where n is some integer Where do I go from here?
73192
Prove: If $a\mid m$ and $b\mid m$ and $\gcd(a,b)=1$ then $ab\mid m$  I thought that $m=ab$ but I was given a counterexample in a comment below.  So all I really know is $m=ax$ and $m=by$ for some $x,y \in \mathbb Z$. Also, $a$ and $b$ are relatively prime since $\gcd(a,b)=1$.   One of the comments suggests to use , i.e., $aq+br=1$ for some $q,r\in\mathbb{Z}$. Any more hints?  New to this divisibility/gcd stuff. Thanks in advance!
1749
Suppose that $p$ is a prime. Suppose further that $h$ and $k$ are non-negative integers such that $h + k = p − 1$.   I want to prove that $h!k! + (−1)^h \equiv 0 \pmod{p}$  My first thought is that by Wilson's theorem, $(p-1)! \equiv -1 \pmod{p}$, and $h!k!$ divides $(p-1)!$ (definition of a binomial). Where would I go from here?
30113
Take $p_1, p_2, \ldots, p_n, p_{n+1}$ be $n+1$ prime numbers in $\mathbb{P} \subseteq \mathbb{N}$. $\sqrt{p_{n+1}} \notin \mathbb{Q}(\sqrt{p_1}, \sqrt{p_2}, \ldots, \sqrt{p_n})$ seems to be quite clear, but still need a proof. I know some proofs are involved with Galois theory, which is not I want.
36993
Prove that if $p$ and $q$ are odd primes and $q$ can divide $a^p-1$, then either $q$ divides $a-1$ or else $q=2kp+1$ for some integer $k$.  I thought the supposition is $a\equiv 1 (mod\ q)$. So $$(a-1)(a^{p-1}+a^{p-2}+...+1) \equiv 0 (mod\ q)$$ Then I proved $q$ may divide $a-1$. But I don't know how to check that $q=2kp+1$. thks
38510
Prove: If a prime number $p\in \mathbb N$ is from the form $p=4k+3,k\in \mathbb N$, then its also a prime number in $\mathbb Z[i]$,i.e. if $p|(z_1\cdot z_2)$ then $p|z_1$ or $p|z_2$.  I dont have any idea how to solve it, so I am looking for some hints.  Thanks in advance :)
12833
Let $a,b,c$ be $3$ distinct integers, and let $P$ be a polynomial with integer coefficients.Show that in this case the conditions $$P(a)=b,P(b)=c,P(c)=a$$ cannot be satisfied simultaneously.  Any hint would be appreciated.
4827
I came across this problem and I believe Lagrange's theorem is the key to its solution.  The question is:     Let $p$ be an odd prime. Prove that there is some integer $x$ such that $x^2 \equiv −1 \pmod p$ if and only if $p \equiv 1 \pmod 4$.   I appreciate any help.  Thanks.
119566
Let x,n ∈ $\mathbb{N}$  such that :  1+$x^1$+$x^2$+$x^3$+....+$x^{n-1}$ is prime .  Proof that n is prime .  I actually suppose that n isn't prime absurdly so n=p×k such as p is prime ,I also use the $a^n$-$b^n$ formula  and find that $x^k$-1/$x^1$-1 so that means that k=1 and then  n=p which is absurd. Does Anyone has another answer ?
113587
Hello everyone this is my first question here so if there are any suggested edits  feel free to participate! Is it true that for every $n$ there two prime numbers $p$ and $q$ with $n\mid p-q$? I have verified this empirically but  am not sure if there is a proof for this
52713
The problem statement is: for $a,b$ coprime, prove that there exists positive integers $x,y$ such that $ax-by=1$.  The question is form Arthur Egnels' problem solving text, and from the chapter on the pigeonhole principle.    My question: His proof begins by generating a list $a,\ldots,a(b-1)$, where he then points out that each element in this list(which proceeds sequentially) doesn't have remainder $0\pmod{b}$.  He then shows that we arrive at a contradiction if we assume that we also don't get remainder $1$ in this list $\bmod b$.  To show the contradiction in this last statement, he first states that we would have positive integers $p,q $ where $ 0&lt;p&lt;q&lt;b$ so that $pa\equiv qa \pmod{b}$.  He then goes on to point out that since we $a$ and $b$ are coprime, we then have that $b| q-p$.  I understand the last part here, but don't see why we get $pa\equiv qa \pmod{b}$.  Thanks in advance
47264
Let $a$ and $b$ be positive integers such that $a | b^2, b^2 | a^3, a^3 | b^4, b^4 | a^5, \cdots $ Prove that $a = b$.  My way is as follows: Let $A=v_p(a), B=v_p(b)$ be the exact power of a prime $p$ dividing $a$ and $b$ respectively. Then by assumption, $(2n-1)A \leq 2nB, n=1,2,3,\cdots.$ Hence $A \leq (2n/(2n-1))B$. Taking limit as $n$ tends to infinite yields $A \leq B.$ Likewise, $2nB \leq (2n+1)A, n=1,2,3,\cdots,$ by a similar argument, we have $B \leq A.$ So that $A=B$ and we are done. But I am rather unsatisfied with the proof because it involves limit. I wanna ask if there is any other alternative proof, thank in advances.
4112
I am currently reading the paper "PRIMES is in p" and have come across some notation that I don't quite understand in this following sentence     Consider a prime $q$ that is a factor of $n$ and let $q^k || n$. Then...   What does the notation $q^k || n$ mean here?  The full paper can be found  and the notation described above is used in the proof on page 2
89243
I have tried as follows. Please help to double check the proof! Thank you!  Since $x=p/q$ ($p$, $q$ are integers), $(p/q)^2+(p/q)a+b=0$  So, $(p/q)^2=-b-a(p/q)$  then, $p^2=-bq^2-a(p/q)q^2$  and, $p = \dfrac {q(-bq-a(p/q)q)}{p}$  now, it is clear that $q \mid p$, thus $p/q$ must be an integer.
58706
I'm trying to understand a proof of  which says that in a integral domain every prime element is irreducible:    I didn't understand why this implication $p=ab\implies p|a$ or $p|b$, is not the contrary $p=ab\implies a|p$ and $b|p$ ?  I'm a little confused  Thanks in advance
38927
How can I show that $(n-1)!\equiv-1 \pmod{n}$ if and only if $n$ is prime? Thanks.
68719
If $p$ and $q$ are distinct primes and $a$ be any integer then $a^{pq} -a^q -a^p +a$ is divisible by $pq$.  Factorising we get $a^{pq} -a^q -a^p +a =a^p(a^q -1) - a(a^{q-1}-1)$ and we know $p \mid a^{p-1}-1$ and $q \mid a^{q-1}-1$.  I can't proceed further with the proof. Please Help!
81606
I have come across this question, which reminded me of Fermats little theorem, i dont know if the Fermats theorem is actually in use in the following mathematical statements   an integer a is a coprime with p and a coprime with q (p and q are different prime numbers )then prove that  $$a^{(p-1)(q-1)} \equiv 1(\operatorname{mod} pq) $$  $$p^{q-1}+q^{p-1} \equiv 1(\operatorname{mod} pq)$$  any help would be appreciated, thanks in advance.