I'm supposed to use Bezout's identity to prove this, but I don't really know how. Using purely what is given if $p$ is a prime then it's divisible by only 1 and itself so that means if $p\mid ab$ then $ab=px$, which means that $p=a$ or $p=b$. If $p=b$ then $(p,a)=1$ then $px+ay=1$. Then I get stuck.
18057
The proof is already given in the textbook but I tried other way around.   Proof by contradiction: Let's assume that $p$ doesn't divide $a$ and $p$ doesn't divide $b$, but $p$ divides $ab$. So $\gcd(p,a)=1$ and $\gcd(p,b)=1$. Given that we can construct linear combinations   $sp+ta=1$ together with $up+wb=1$. Multiplying the left and the right sides of the equations we get  $spup+spwb+taup+tawb=1$ or $p(sup+swb+tau)+ab(tw)=1 \implies \gcd(p,ab)=1$. This is a contradiction.   Is it rigorous and sound proof?
39605
A friend asked me this question:     If $p$ is a prime, prove that $(p - 1)! + 1$ is a power of $p$ if and only if $p = 2, 3$ or $5$.   Clearly one direction is obvious, namely that $p=2,3,5$ implies $(p - 1)! + 1$ is a power of $p$.  The other direction is not clear to me. Since by Wilson's theorem $p$ divides $(p - 1)! + 1$ so we need to show that if there are no other prime factors then $p=2,3,5$. Can someone give me a hint for establishing this?  Thanks
30745
Let $p$ be a prime. Show that for all integers $x$, $x^2\equiv 1 (\text{mod} \ p) $ if and only if $x \equiv 1 (\text{mod} \ p)$ or $ x \equiv p-1 \ (\text{mod} \ p ). $    I know that I have to prove this both forward and backward. I'm not really sure where to begin
117611
Let $p$ be a prime such that $a^p-1 \equiv 0 \pmod{p}$. Prove that $\gcd(a,p) = 1$.   We know from Fermat's Little Theorem that $a^{p-1}-1 \equiv 0 \pmod{p}$ if and only if $\gcd(a,p) = 1$, but how do we use this to solve the question?
40611
I wrote:  Since gcd(n-k, n)=1, we can use Bezout's Identity to say: ∃(x,y)∈Z such that (n-k)x+ny=1. Distributing, nx-kx+ny=1. One can then produce the equation: n(x+y)-kx=1. I then stated about how because of that equation, it is proved that gcd(n-k, n)=1. I am almost certain that what I wrote is not the proper way to prove this statement so could someone please present their own version of the proof or explain to me where I messed up?
84624
For which primes $p$ is $2^p+1$ divisible by $p$?  What I have been doing is:  $2^p+1\equiv 0\pmod p$  $2^p\equiv -1\pmod p$  Then by Fermat's Theorem, we get  $2^p\equiv 2\pmod p$  This shows $p=1,3$.  I feel like this is not right though...
493
The following is a well known problem   If $a|b^2; b^2|a^3; a^3|b^4; ....$ then $a=b$.  I started with $a$ is a prime $p$ and the conclusion immediately holds.  So I was comparing powers of primes but can't get anything useful.  Please help.
106565
I'm refreshing some algebra and in the beginning chapters of my book I'm presented with the following simple looking problem that I got stuck on:      Prove or disprove: If $n$ is a positive integer, then $n=p+a^2$, where $a$ is an integer and $p$ is prime or $p=1$.   At first I thought $n=13$ would give a nice counterexample, but then I noticed my book defines primes to include the negative primes. Now $13=-3+4^2$ is a solution.   I am allowed to use the fundamental theorem of arithmetic and the division and euclidean algorithms. I tried to express $n$ and $a$ by their prime factorizations, but I didn't get anywhere from there. I would like a hint which direction to take. Am I just missing something silly?
43674
Calculate for every positive integer $n$ and for every prime $p$ the expression  $$1^n +2^n + \cdots +(p-1)^n \mod p$$    I need your help for this. I don't know what to do, but I'll show you what I know.   Wilson's theorem The identity $X^p-X = \prod_{a \in \mathbb{F}_p-1}(X-a)$ $\exists a \in \mathbb{Z}, \ a^2 \equiv -1 \mod p \qquad \iff \qquad p \equiv 1 \mod 4$   Now can you please provide me a hint?
83845
I am lost.   So far...  If $\gcd (a,b) = 1$, by Bezout's Formula  $ax + by = 1$  If $c|(a+b)$, then $cf = a+b$  Then,  $a (x-y) + cfy = 1$   $b(yx) + cfx = 1$  Am I on the right track? Any suggestions?
15659
Prove that if $d$ is a common divisor of two integers $a$ and $b$, then $d=\gcd(a,b)$ if and only if $\gcd(a/d,b/d)=1$.   So far I used what was given so I have $a=dk$, $b=ld$ and $\gcd(a,b)=d$ can be written as a linear combination of $ax+by=d$ but I am unsure how to use the information.   Where do I go from here? Can someone show me how to solve this using Bezout's Identity if possible?
122670
... namely that if $n &gt; 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime.  This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it concretely..  Reason by contradiction, suppose that $n$ is not prime.   Then $n = ab$, where $1 &lt; a, b &lt; n$  In particular $(n-1)! = ai$ for some $i\in\Bbb{Z}$. $\\$ If $(n-1)! = nj - 1$ for some $j\in\Bbb{Z}$ then it follows that a probably doesn't divide $-1$?
108006
We were given the following problem as an assignment, we proved the converse in class for prime numbers; however, we can't use the assumption that $\operatorname{gcd}(a,b) = 1$.  So I am struggling to think of my first possible move.  We are given $ar + bs = 1$, the only think I can think of is let $d$ be a common divisor or $ar + bs$ and then show that the $d = 1$.  However, I am not really sure how to do that.  If anyone could just give me a hint or two to nudge me in the right direction I would be appreciative.
53347
Prove that if $m\not =n,a$ are positive integers then $(a^{2^n}+1,a^{2^m}+1)$ is $1$ if $a$ is even and $2$ if $a$ is odd.    I solve the problem in the following way: I assume that $m&gt;n$ then  $$a^{2^m}+1=a^{2^m}-1+2$$ With this expression if I take a divisor prime $p$ of $a^{2^n}+1$ then if $p|a^{2^m}+1$ this prime must divide 2 and the result follows.   But, how can I prove this statement without use of primes? This exercise appears before the concept of prime is introduced then I prefer do not use it.    Any idea?   Thanks!
59040
If $p$ is a prime number and $r = 1,2,3 \dots ,p -1$, how can I prove that the binomial coefficients $_nC_r(p,r)$ are divisible by $p$? By divisible I mean $_nC_r(p,r)/p$ leaves remainder $0$.  oivind
105138
if $p&gt;6$ is prime then 1920 divides $p^4-10p^2+9$ Take out the factors of 1920 which are $$1920=2^7(3)(5)$$ and factor the expression that remains as $$p^4-10p^2+9=(p-3)(p-1)(p+1)(p+3)$$ and I assumed as p is prime then p-1 and p + 1 is even then it is divisible by $2^7$ but I think it is not correct, can you help me?
68102
I have thought a lot but am failing to arrive at anything encouraging.   First try: If this is to be proved by contradiction, then I start with the assumption that let $n$ be a number which is a sum of two numbers, of which at least one is prime. This gives $n = p + c$, where $p$ is the prime number and $c$ is the composite number. Also, any composite number can be written as a product of primes. So I can say, $n = p + p_1^{e_1}.p_2^{e_2}...p_k^{e_k}$. From this, I get $n - p = p_1^{e_1}.p_2^{e_2}...p_k^{e_k}$, but I have no clue what to do next.  Second try: For an instant let me forget about contradiction. Since $n &gt; 11$, I can say that $n \geq 12$. This means that either $p \geq 6$ or $c \geq 6$. Again I'm not sure what to do next.  Finally, consider that the number 20 can be expressed in three different ways: $17+3$ (both prime), $16+4$ (both composite), and $18+2$ (one prime and one composite). This makes me wonder what we are trying to prove.  The textbook contains a hint, "Can all three of $n-4$, $n-6$, $n-8$ be prime?", but I'm sure what's so special about $4, 6, 8$ here.