0
$\begingroup$

I found this exercise in Beachy and Blair: Abstract algebra:

Prove that $$ 4(n^2+1) $$ is never divisible by $11$.

(I assume $n\in\mathbb{Z}$ although this is not given in the book)

I tried with contradiction, that is assuming that $$ 4(n^2+1)\equiv 0 \quad (\mathrm{mod} \ 11) $$ which we can write as $$ 4(n^2+1)=11k\qquad k\in\mathbb{Z} $$ and I tried to reduce this modulo to reach a contradiction but I failed to arrive at any contradiction. Maybe I tried wrong moduli or I missed something or maybe there is a better way to tackle this.

Can someone provide me some HINTS?

Thank you!

$\endgroup$
  • $\begingroup$ HINT: quadratic reciprocity. $\endgroup$ – Kenny Lau Oct 25 '17 at 8:04
  • $\begingroup$ Start by solving the equation $4(x + 1) = 0$ modulo $11$. You'll need to decide if $4$ has a multiplicative inverse modulo $11$. $\endgroup$ – Theo Bendit Oct 25 '17 at 8:07
  • 1
    $\begingroup$ solve $n^2\equiv 10 \pmod {11}$ $\endgroup$ – MCCCS Oct 25 '17 at 8:11
4
$\begingroup$

For any modulus $m$ there are at most $m/2+1$ different possibilities for $n^2$ (mod $m$). This is because $n^2\equiv(m-n)^2$, so the numbers mod $m$ (other than $0$ and $m/2$) divide into pairs with the same square.

Your equation has a solution if and only if $n^2+1\equiv 0$ mod $11$ has a solution, i.e. if and only if $n^2\equiv 10$ (mod $11$) has a solution. You can check that this isn't the case by working out $0^2,1^2,...,5^2$ mod $11$ (you don't need to check $6^2,...10^2$ because these are the same as $5^2,...1^2$).

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

$4(n^2+1)$ is divisible by $11$ if and only if $n^2+1$ is divisible by $11$ (because $4$ is invertible), which happens if and only if $n^2 \equiv -1 \pmod {11}$, which happens if and only if $-1$ is a quadratic residue $\pmod {11}$, which (by Euler's criterion) happens if and only if $(-1)^{(11-1)/2}$ is congruent to $1$, which it isn't.


The justification behind Euler's criterion is that there is a primitive root modulo any prime, meaning that you can always find $a$ such that for any non-zero number there is an $n$ such that $a^n$ is congruent to the number. Then, being a quadratic residue $\pmod p$ is equivalent to being congruent to $a^m$ for some even $m$. By Fermat's little theorem, $a^{p-1} \equiv 1 \pmod p$. We know that an even number, when multiplied by $\dfrac{p-1}2$ is a multiple of $p-1$, while an odd number has no such property. Hence, if $m$ is even, then $a^{m(p-1)/2} \equiv (a^{p-1})^{m/2} \equiv 1^{m/2} = 1$ (the middle step is permissible because $m/2$ is an integer).

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

For a number to be divisible by $11$ it must be a multiple of $11$.
$$ 4(n^2+1) $$.
clearly the product of this would be even, because of the standing $4$.
if this was even and $n$ was a real positive integer.
then $(n^2+1)$ must be a multiple of $11$.
say.
$$ \begin{align} (n^2 + 1) = 11x\\ n^2 = 11x - 1\\ n = \sqrt{11x - 1} \end{align} $$.
so we are left to prove whether $(11x-1)$ is a perfect square or not.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I haven't got enough rep points yet to leave a comment, but I'm not going to give you the full answer.
Since the book is on Abstract Algebra, they probably want you to work in the finite field of integers mod 11. Yes you started down a path which will work.
THE BIG HINT IS look at which of the elements of the field which are squares. Restrict your investigation to those squares. Modify that set to get the answer.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Once you have got to seeing whether $-1$ is a square modulo $11$, you might note that the multiplicative group of residues ("units") modulo $11$ has order $10$ and that if $a^2\equiv -1$ then $a^4\equiv 1$ and $a$ has order $4$, which is a contradiction - a group of order $10$ can't have an element of order $4$.

If $p$ is a prime $\equiv 3 \bmod 4$ you can use a similar argument to show that $-1$ is not a square modulo $p$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.