Prove: If the integer ## a ## is not divisible by ## 2 ## or ## 3 ##....

[Math100]

Homework Statement

Prove the assertion below:
If the integer $a$ is not divisible by $2$ or $3$, then $a^{2}\equiv 1\pmod {24}$.

Relevant Equations

None.

Proof:

Suppose that the integer $a$ is not divisible by $2$ or $3$.
Then $a\equiv 1, 5, 7, 11, 13, 17, 19$ or $23\pmod {24}$.
Note that $a\equiv b\pmod {n}\implies a^{2}\equiv b^{2}\pmod {n}$.
Thus $a^{2}\equiv 1, 25, 49, 121, 169, 289, 361$ or $529\pmod {24}\implies a^{2}\equiv 1\pmod {24}$.
Therefore, if the integer $a$ is not divisible by $2$ or $3$, then $a^{2}\equiv 1\pmod {24}$.

 

[fresh_42]

Homework Statement:: Prove the assertion below:
If the integer $a$ is not divisible by $2$ or $3$, then $a^{2}\equiv 1\pmod {24}$.
Relevant Equations:: None.

Proof:

Suppose that the integer $a$ is not divisible by $2$ or $3$.
Then $a\equiv 1, 5, 7, 11, 13, 17, 19$ or $23\pmod {24}$.
Note that $a\equiv b\pmod {n}\implies a^{2}\equiv b^{2}\pmod {n}$.
Thus $a^{2}\equiv 1, 25, 49, 121, 169, 289, 361$ or $529\pmod {24}\implies a^{2}\equiv 1\pmod {24}$.
Therefore, if the integer $a$ is not divisible by $2$ or $3$, then $a^{2}\equiv 1\pmod {24}$.

Correct, but you could have explained the first "Then" a bit. It is clear that $a$ cannot be even, so it cannot be even modulo $24$ either. What rules out $3,9,15,21$?

(I know what. I only think that a little remark would have been helpful.)

 

[Math100]

Correct, but you could have explained the first "Then" a bit. It is clear that $a$ cannot be even, so it cannot be even modulo $24$ either. What rules out $3,9,15,21$?

(I know what. I only think that a little remark would have been helpful.)

The fact that $3\nmid a$, rules out $3, 9, 15, 21$.

 

[fresh_42]

The fact that $3\nmid a$, rules out $3, 9, 15, 21$.

I know. But a line like $a= 24m + 3k=3\cdot (8m+k)$ would have made it visible. It was just a suggestion since this is the only step that isn't immediately obvious. At least to me.

 

[Math100]

I know. But a line like $a= 24m + 3k=3\cdot (8m+k)$ would have made it visible. It was just a suggestion since this is the only step that isn't immediately obvious. At least to me.

Where should I insert this line then?

 

[fresh_42]

I thought about the following:

Proof:

Suppose that the integer $a$ is not divisible by $2$ or $3$.

This means $a=24s+ 2t= 2\cdot (12s+t)$ or $a=24s+3t=3\cdot (8s+t)$ cannot occur and the only possible remainders are ...

Then $a\equiv 1, 5, 7, 11, 13, 17, 19$ or $23\pmod {24}$.
Note that $a\equiv b\pmod {n}\implies a^{2}\equiv b^{2}\pmod {n}$.
Thus $a^{2}\equiv 1, 25, 49, 121, 169, 289, 361$ or $529\pmod {24}\implies a^{2}\equiv 1\pmod {24}$.
Therefore, if the integer $a$ is not divisible by $2$ or $3$, then $a^{2}\equiv 1\pmod {24}$.

However, your proof was ok. That was only a suggestion for lazybones like me (and consider my local time of 0:35 p.m.).

 

[Math100]

Thank you for your suggestion.

 

[Delta2]

The statement of the problem looks a bit ambiguous to me.

When we say "not divisible by 2 or 3" do we mean :
((NOT divisible by 2) OR (NOT divisible by 3)))
or do we mean
(NOT (divisible by 2 OR divisible by 3))=(NOT divisible by 2) AND (NOT divisible by 3).

From the way the proof goes I think we mean the 2nd interpretation :).

 

[fresh_42]

The statement of the problem looks a bit ambiguous to me.

That is automatically always the case whenever NOT meets AND or OR. Langauge is bad with parentheses. However, it is relatively easy to see that $(2\cdot 3)^2 \not\equiv 1 \pmod {24}$ which answers any ambiguities.

 

[epenguin]

Correct, but you could have explained the first "Then" a bit. It is clear that $a$ cannot be even, so it cannot be even modulo $24$ either. What rules out $3,9,15,21$?

(I know what. I only think that a little remark would have been helpful.)

Yes, I think he has merely listed the squares of his first list. He could have said so, it takes a moment to realize.

Math100 seems to have corrected his previous tendency to nonlogical/ incomplete or irrelevant arguments, and is now tending to great succinctness. Not exactly wrong, but if too much he could easily find if he comes back to these things after a year it has become hard for him to know what his reasonings were.