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

  • Thread starter Math100
  • Start date
  • Tags
    Integer
In summary, the proof states that if a number is not divisible by 2 or 3, then it is equal to 1, 5, 7, 11, 13, 17, 19, or 23 mod 24.
  • #1
Math100
756
204
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} ##.
 
  • Like
Likes Delta2 and fresh_42
Physics news on Phys.org
  • #2
Math100 said:
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.)
 
  • Like
Likes Math100
  • #3
fresh_42 said:
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 ##.
 
  • #4
Math100 said:
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.
 
  • #5
fresh_42 said:
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?
 
  • #6
I thought about the following:

Math100 said:
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 ...
Math100 said:
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.).
 
  • Like
Likes Math100
  • #7
Thank you for your suggestion.
 
  • #8
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 :).
 
Last edited:
  • #9
Delta2 said:
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.
 
  • Informative
Likes Delta2
  • #10
fresh_42 said:
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.
 

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

1. What does it mean for an integer to be divisible by 2 or 3?

An integer is divisible by 2 if it can be divided evenly by 2 without any remainder. Similarly, an integer is divisible by 3 if it can be divided evenly by 3 without any remainder. In other words, if the result of dividing the integer by 2 or 3 is a whole number, then it is divisible by 2 or 3.

2. What is the significance of proving that an integer is not divisible by 2 or 3?

Proving that an integer is not divisible by 2 or 3 is important because it helps us understand the divisibility properties of numbers. It also allows us to identify prime numbers, which are numbers that are only divisible by 1 and itself.

3. How can we prove that an integer is not divisible by 2 or 3?

To prove that an integer is not divisible by 2 or 3, we can use the method of contradiction. We assume that the integer is divisible by 2 or 3 and then show that this leads to a contradiction. This means that our initial assumption was wrong and the integer is not divisible by 2 or 3.

4. Can an integer be divisible by both 2 and 3?

Yes, an integer can be divisible by both 2 and 3. For example, the number 6 is divisible by both 2 and 3 because it can be divided evenly by 2 and 3 without any remainder.

5. What is the relationship between divisibility by 2 and 3 and divisibility by 6?

If an integer is divisible by both 2 and 3, then it is also divisible by 6. This is because 6 is the smallest number that is divisible by both 2 and 3. In other words, if an integer is divisible by 6, then it must also be divisible by both 2 and 3.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
1
Views
2K
  • Precalculus Mathematics Homework Help
Replies
3
Views
860
  • Precalculus Mathematics Homework Help
Replies
3
Views
918
  • Precalculus Mathematics Homework Help
Replies
2
Views
843
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
962
  • Precalculus Mathematics Homework Help
Replies
6
Views
860
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
815
Back
Top