1
$\begingroup$

I am trying to self-study mathematics and I got stuck in this question. I did not find similar questions to this elsewhere so I am asking this one.

Also if you may please answer this follow up question:

Prove using mathematical induction that $x^2 - 1$ is divisible by $3$ for all positive integers $x$ that are not divisible by $3$.

Prove that for all positive integers $x, \ x$ is not divisible by $3 \iff {x^2 - 1} $ is divisible by $3$.

$\endgroup$
3
$\begingroup$

Hint : One of the numbers $x-1,x,x+1$ must be divisible by $3$

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

Try re-writing $ x^2-1 $ using the difference of two squares: $$ x^2 - 1 = (x+1)(x-1)$$ If we know that this is a multiple of 3, then what can you say about $x+1$ and $x-1$?

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

Hint:

The sequence of $(n^2-1)\bmod 3$ is $2,0,0,2,0,0,2,0,0,\cdots$

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

Use congruences:

A number $x$ is divisible by $3$ iff $x\equiv 0\bmod 3$. A number $x$ is not divisible by $3$ iff $x\equiv 1$ or $-1\bmod 3$, and in this single case, $x^2\equiv 1\bmod 3$.

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

$\Leftarrow:$

Assume $3|(x^2-1)$;

Then $3|(x-1)(x+1)$;

Euclid's lemma:

$3|(x-1)$ or $3|(x+1)$, hence $3 \not | x$;

$\Rightarrow:$

Assume $3\not | x$;

We have $3| (x-1)(x)(x+1)$, three consecutive integers.

Euclid's lemma:

$3|(x-1)$ or $3|(x+1)$, hence

$3|(x-1)(x+1)$, and we are done.

| 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.