I have been stuck on this problem for awhile.  How would i go about solving it, an explanation would be helpful as well.  Show that if $n$ is an integer then $n^2 \equiv 0$ or $1 \pmod 4$?
35080
This is a question from the free Harvard online abstract algebra .  I'm posting my solutions here to get some feedback on them.  For a fuller explanation, see  post.  This problem is from assignment 6.  The notes from this lecture can be found .     a) Prove that the square $a^2$ of an integer $a$ is congruent to 0 or 1 modulo 4.   b) What are the possible values of $a^2$ modulo 8?   a) Let $a$ be an integer. Then $a=4q+r, 0\leq r&lt;4$ with $\bar{a}=\bar{r}$.  Then we have $a^2=a\cdot a=(4q+r)^2=16q^2+8qr+r^2=4(4q^2+2qr)+r^2, 0\leq r^2&lt;4$ with $\bar{a^2}=\bar{r^2}$.  So then the possible values for $r$ with $r^2&lt;4$ are 0,1.  Then $\bar{a^2}=\bar{0}$ or $\bar{1}$.  b) Let $a$ be an integer. Then $a=8q+r, 0\leq r&lt;8$ with $\bar{a}=\bar{r}$.  Then we have $a^2=a\cdot a=(8q+r)^2=64q^2+16qr+r^2=8(8q^2+2qr)+r^2, 0\leq r^2&lt;8$ with $\bar{a^2}=\bar{r^2}$.  So then the possible values for $r$ with $r^2&lt;8$ are 0,1,and 2.  Then $\bar{a^2}=\bar{0}$, $\bar{1}$ or $\bar{4}$.  Again, I welcome any critique of my reasoning and/or my style as well as alternative solutions to the problem.  Thanks.
56173
Prove $x \equiv a \pmod{p}$ and $x \equiv a \pmod{q}$ then $x \equiv a\pmod{pq}$ for $p\neq q$ distinct primes.  Where can I start with this proof? It looks similar to the Chinese Remainder Theorem, but that deals with two different a values.
25053
$\forall m,n\in\mathbb Z$ , $m\ge1$ and $n\ge1$ how to prove that  $$\frac{(mn)!}{m!(n!)^m}$$ is an integer?  Thanks in advance.
35054
Which of the following primes satisfy the congruence   $$a^{24}\equiv6a+2\pmod{13}$$  1) 41  2) 47  3) 67  4) 83  I am interested in Theorem statement, corollary, or Trick or Logic which solves this problem within one minute. Thank you in Advance
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.
85930
An integer $n$ is a perfect square if and only if it can be expressed as the square of some other integer i.e. there exists some integer $a$ such that $n=a^2$.    Prove that if $n$ is a perfect square, then either $n \equiv 1 ~(\mod 4)$, or $n \equiv 0 ~(\mod 4)$.  How can I prove this?
81326
We have to find the integers $m$ and $n$ which will satisfy the given condition: $$m^2-n^2=1111.$$  What could be the answer and how? i tried using trial and error and that took a long time.
44490
I realize that there is a similar post to this, but that post included a hint which we were not given. Also regarding that hint, I'm just wondering how someone could find it out for themselves. Here is the related post:  I know that $F_n = 2^{2^n} + 1$ and therefore $\,2^{2^n} \equiv -1 \pmod{F_n}$. But I don't intuitively know the next step to take to show that $\ 2^{F_n}\equiv 2\pmod{\!F_n},\,$ i.e. that  $$2^{2^{2^n} + 1} \equiv 2 \pmod{2^{2^n}+1}$$ So in essence, I would like to know how to solve it without knowing the hint. Thank you.
77523
I've been asked to show that:  $n(n+1)(2n+1) \equiv 0 \pmod 6$  I found in a previous question that:  $n(n+1)$ was divisible by $2$ and resulted in an even number e.g  $n(n+1) \equiv 0 \pmod 2$  so I figured I needed to find:  $(2n+1) \equiv 0 \pmod 3$ in order to complete  $n(n+1)(2n+1) \equiv 0 \pmod 6$  but I am unsure on how to find $(2n+1) \equiv 0 \pmod 3$  Is this the right way to find the mod 6 and if so could you tell me how I could find  $(2n+1) \equiv 0 \pmod 3?$
72318
I have not been able to solve this problem. Any insights would be appreciated!   Let $x, n > 1$ be integers. Suppose that for each $k > 1$ there exists an integer $a_{k}$ such that $x − a_k^n$ is divisible by $k$. Prove that $x = A^{n}$ for some integer $A$.
2770
Show that if $n&gt;2$, then $(n!)^2&gt;n^n$.     My work: I tried to apply induction. So, at the induction step, I need to prove, $n^n&gt;(n+1)^{n-1}$ Here, I tried to use induction again without any luck. I also took log of both sides, but I did not get anything. Please help!
28336
Find all positive integers $n$ such that $a \equiv a^{-1} \pmod{n}$ for all invertible $a$ modulo $n$.   I found that $n = 1,2,4,6,8,12,24$ satisfy this. How can we prove that these are all of them?
85098
I need help!  I need to prove that for any $2 \le n,k$ positive integers $(n - 1)^2 \mid n^k -1$ if and only if $(n - 1) \mid k$  Thanks!
38732
Prove that $$\frac{(n+1)(n)^2(n-1)^2...(n-k+2)^2(n-k+1)}{(k+1)(k)^2(k-1)^2...(2)^2(1)}$$ is or is not an integer for $0\leq k \leq n$, where $k$ and $n$ are integer values. This looks like $\frac{(n+1)!(n)!}{(n-k+1)(n-k)(k+1)!(k)!}$. The above statement is true for k=1 and k=2 as seen by observing modular residues. Not sure how to proceed.
61754
Problem:   If $x^{n-1} \equiv 1 \pmod{n}$, and for all divisors $q$ of $n - 1$, $a^{q} \not\equiv 1 \pmod{n}$, then $n$ is prime. $(n &gt; 1)$   I read the proof in the book and it was very straightforward; however, I wonder is there a way to prove it by just using congruence property?    And another related question about power residue: If we have $a^{n - 1} \equiv 1 \pmod{n}$. Is there any relation between $n - 1$ and $\phi(n)$?  Because I thought of $a^{\phi(n)} \equiv 1 \pmod{n}$, when $(a, n) = 1$. I try to think of away to connect these two ideas, but I still cannot see it. Any idea?    Thanks,
108341
How to solve and see resolution of $13^{53} \pmod 7$ using Fermat little Theorem? Using , I know it gives me 6 as an answer to this problem..., but why? How is the resolution? Thanks,
74594
Using permutation or otherwise, prove that $\displaystyle \frac{(n^2)!}{(n!)^n}$ is an integer,where $n$ is a positive integer.  I have no idea how to prove this..!!I am not able to even start this Can u give some hints or the solution.!cheers.!!