# Show that ## 168=3\cdot 7\cdot 8 ## divides ## a^{6}-1 ##

• Math100
In summary: I have to use this additional line, too, given the fact that I am not a number theorist. In fact, I got the ## a^{2}\equiv 1\pmod {8} ## part, mainly because ## a ## is odd and so ## a>0, a\geq 3 ##, that's why I plugged in ## a=3 ## and got ## a^{2}=9, a^{2}\equiv 1\pmod {8} ##, but I think this is vague, just as you mentioned above, I should have explained this.
Math100
Homework Statement
If ## gcd(a, 42)=1 ##, show that ## 168=3\cdot 7\cdot 8 ## divides ## a^{6}-1 ##.
Relevant Equations
None.
Proof:

Suppose ## gcd(a, 42)=1 ##.
Then ## 42=2\cdot 3\cdot 7 ## and ## gcd(a, 2)=gcd(a, 3)=gcd(a, 7)=1 ##.
Applying the Fermat's theorem produces:
## a\equiv 1\pmod {2}, a^{2}\equiv 1\pmod {3} ## and ## a^{6}\equiv 1\pmod {7} ##.
This means ## a^{6}=(a^{2})^{3}\equiv 1\pmod {3} ##.
Observe that ## a^{6}-1=(a^{3}-1)(a^{3}+1)=(a-1)(a+1)(a^{2}+a+1)(a^{2}-a+1) ##.
Since ## a ## is odd, it follows that ## a>0\implies a\geq 3 ##.
Now we have ## a^{2}\equiv 1\pmod {8}\implies (a^{2})^{3}\equiv 1^{3}\pmod {8}\implies a^{6}\equiv 1\pmod {8} ##.
Thus, ## 168\mid (a^{6}-1) ## because ## 3, 7, 8 ## are relatively prime to each other.
Therefore, if ## gcd(a, 42)=1 ##, then ## 168=3\cdot 7\cdot 8 ## divides ## a^{6}-1 ##.

Math100 said:
Homework Statement:: If ## gcd(a, 42)=1 ##, show that ## 168=3\cdot 7\cdot 8 ## divides ## a^{6}-1 ##.
Relevant Equations:: None.

Proof:

Suppose ## gcd(a, 42)=1 ##.
Then ## 42=2\cdot 3\cdot 7 ## and ## gcd(a, 2)=gcd(a, 3)=gcd(a, 7)=1 ##.
Applying the Fermat's theorem produces:
## a\equiv 1\pmod {2}, a^{2}\equiv 1\pmod {3} ## and ## a^{6}\equiv 1\pmod {7} ##.
This means ## a^{6}=(a^{2})^{3}\equiv 1\pmod {3} ##.
Observe that ## a^{6}-1=(a^{3}-1)(a^{3}+1)=(a-1)(a+1)(a^{2}+a+1)(a^{2}-a+1) ##.
Since ## a ## is odd, it follows that ## a>0\implies a\geq 3 ##.
Now we have ## a^{2}\equiv 1\pmod {8}\implies (a^{2})^{3}\equiv 1^{3}\pmod {8}\implies a^{6}\equiv 1\pmod {8} ##.
Thus, ## 168\mid (a^{6}-1) ## because ## 3, 7, 8 ## are relatively prime to each other.
Therefore, if ## gcd(a, 42)=1 ##, then ## 168=3\cdot 7\cdot 8 ## divides ## a^{6}-1 ##.
Right, but what did you use the factorization of ##a^6-1## for? Instead, you should have explained ##a^2\equiv 1\pmod{8}.## E.g. by ##(2k+1)^2=4k(k+1)+1## where either ##k## or ##k+1## is even.

fresh_42 said:
Right, but what did you use the factorization of ##a^6-1## for? Instead, you should have explained ##a^2\equiv 1\pmod{8}.## E.g. by ##(2k+1)^2=4k(k+1)+1## where either ##k## or ##k+1## is even.
Absolutely nothing. Now, I just realized that I shouldn't factor out ## a^{6}-1 ##, because like you mentioned, I didn't use this on anything in this proof. Also, for the ## a^{2}\equiv 1\pmod {8} ## part, are you saying that letting ## a=2k+1 ## where ## k=2m ## for some ## k\in\mathbb{Z} ## can help better explain where we got the ## a^{2}\equiv 1\pmod {8} ## part from?

Math100 said:
Absolutely nothing. Now, I just realized that I shouldn't factor out ## a^{6}-1 ##, because like you mentioned, I didn't use this on anything in this proof. Also, for the ## a^{2}\equiv 1\pmod {8} ## part, are you saying that letting ## a=2k+1 ## where ## k=2m ## for some ## k\in\mathbb{Z} ## can help better explain where we got the ## a^{2}\equiv 1\pmod {8} ## part from?
Number theorists have it probably in mind: ##a\equiv 1\pmod{2}\Longrightarrow a^2\equiv 1\pmod{8}## but I had to use this additional line. From ##a\equiv 1\pmod{2}## we get ##a=2k+1## and ##a^2=4k(k+1)+1.## This shows ##a^2\equiv 1\pmod{8}## no matter whether ##k## is odd or even because ##\{k,k+1\}## always contains an even number.

Last edited:
Math100
fresh_42 said:
Number theorists have it probably in mind: ##a\equiv 1\pmod{2}\Longrightarrow a^2\equiv 1\pmod{8}## but I had to use this additional line. From ##a\equiv 1\pmod{2}## we get ##a=2k+1## and ##a^2=4k(k+1)+1.## This shows ##a^2\equiv 1\pmod{8}## no matter whether ##k## is odd or even because ##\{k,k+1\}## always contains an even number.
I have to use this additional line, too, given the fact that I am not a number theorist. In fact, I got the ## a^{2}\equiv 1\pmod {8} ## part, mainly because ## a ## is odd and so ## a>0, a\geq 3 ##, that's why I plugged in ## a=3 ## and got ## a^{2}=9, a^{2}\equiv 1\pmod {8} ##, but I think this is vague, just as you mentioned above, I should have explained this. Thank you for the additional line.

## 1. What does it mean for a number to divide another number?

When a number, called the divisor, divides another number, called the dividend, it means that the result of the division is a whole number without any remainder. In other words, the dividend is evenly divisible by the divisor.

## 2. How do you show that 168 divides a6-1?

To show that 168 divides a6-1, we need to prove that a6-1 is divisible by 3, 7, and 8, since 168 is the product of these three numbers. This can be done using the rules of divisibility, such as the fact that a number is divisible by 3 if the sum of its digits is divisible by 3.

## 3. Why is it important to show that 168 divides a6-1?

It is important to show that 168 divides a6-1 because it helps us understand the properties of the numbers involved. It also allows us to simplify expressions and solve equations involving these numbers more easily.

## 4. Can you provide an example to demonstrate the divisibility of 168?

Yes, for example, if we let a=5, then a6-1=15624-1=15623. We can see that 15623 is divisible by 3, 7, and 8, since the sum of its digits is 17, which is divisible by 3, and the last three digits form a number that is divisible by 8. Therefore, we can conclude that 168 divides 15623.

## 5. What are the applications of showing that 168 divides a6-1?

The applications of showing that 168 divides a6-1 are numerous, as it allows us to simplify and solve various mathematical problems involving these numbers. For example, it can be used in algebraic manipulations, number theory, and cryptography.

Replies
3
Views
947
Replies
6
Views
1K
Replies
2
Views
1K
Replies
1
Views
1K
Replies
7
Views
2K
Replies
2
Views
1K
Replies
14
Views
1K
Replies
7
Views
2K
Replies
4
Views
1K
Replies
19
Views
1K