Show that ## 60 ## divides ## a^{4}+59 ##

  • Thread starter Math100
  • Start date
In summary: Therefore, ## a^{4}\equiv 1\pmod {4} ##. Overall, this shows that ## a^{4}\equiv 1\pmod {60} ##. In summary, if ## gcd(a, 30)=1 ##, then ## 60 ## divides ## a^{4}+59 ##.
  • #1
Math100
779
220
Homework Statement
If ## gcd(a, 30)=1 ##, show that ## 60 ## divides ## a^{4}+59 ##.
Relevant Equations
None.
Proof:

Suppose ## gcd(a, 30)=1 ##.
Then ## 30=2\cdot 3\cdot 5 ## and ## gcd(a, 2)=gcd(a, 3)=gcd(a, 5)=1 ##.
Applying the Fermat's theorem produces:
## a\equiv 1\pmod {2}, a^{2}\equiv 1\pmod {3} ## and ## a^{4}\equiv 1\pmod {5} ##.
This means ## gcd(a, 4)=gcd(a, 2^{2})=1 ##.
Observe that
\begin{align*}
&a\equiv 1\pmod {2}\implies a^{2}\equiv 1\pmod {2}\\
&a^{2}\equiv 1\pmod {3}\implies a^{4}\equiv 1\pmod {3}.\\
\end{align*}
Now we have ## 2\mid (a^{2}-1)\implies a^{2}\equiv (1-2)\pmod {2}\equiv -1\pmod {2} ##,
so ## 4\mid (a^{2}+1)(a^{2}-1)\implies 4\mid (a^{4}-1) ##.
Since ## 60=3\cdot 4\cdot 5 ## and ## 3, 4, 5 ## are relatively prime to each other,
it follows that ## 60\mid (a^{4}-1) ##.
Thus ## a^{4}\equiv 1\pmod {60}\equiv (1-60)\pmod {60}\equiv -59\pmod {60} ##.
Therefore, if ## gcd(a, 30)=1 ##, then ## 60 ## divides ## a^{4}+59 ##.
 
Physics news on Phys.org
  • #2
Math100 said:
Homework Statement:: If ## gcd(a, 30)=1 ##, show that ## 60 ## divides ## a^{4}+59 ##.
Relevant Equations:: None.

Proof:

Suppose ## gcd(a, 30)=1 ##.
Then ## 30=2\cdot 3\cdot 5 ## and ## gcd(a, 2)=gcd(a, 3)=gcd(a, 5)=1 ##.
Applying the Fermat's theorem produces:
## a\equiv 1\pmod {2}, a^{2}\equiv 1\pmod {3} ## and ## a^{4}\equiv 1\pmod {5} ##.
This means ## gcd(a, 4)=gcd(a, 2^{2})=1 ##.
Observe that
\begin{align*}
&a\equiv 1\pmod {2}\implies a^{2}\equiv 1\pmod {2}\\
&a^{2}\equiv 1\pmod {3}\implies a^{4}\equiv 1\pmod {3}.\\
\end{align*}
Now we have ## 2\mid (a^{2}-1)\implies a^{2}\equiv (1-2)\pmod {2}\equiv -1\pmod {2} ##,
so ## 4\mid (a^{2}+1)(a^{2}-1)\implies 4\mid (a^{4}-1) ##.
Since ## 60=3\cdot 4\cdot 5 ## and ## 3, 4, 5 ## are relatively prime to each other,
it follows that ## 60\mid (a^{4}-1) ##.
Thus ## a^{4}\equiv 1\pmod {60}\equiv (1-60)\pmod {60}\equiv -59\pmod {60} ##.
Therefore, if ## gcd(a, 30)=1 ##, then ## 60 ## divides ## a^{4}+59 ##.
The modulo ##2## case is a bit messy.

We have ##a\equiv 1\pmod{2}## so ##a^2\equiv 1\pmod{2}##. But then, ##a^2+1## and ##a^2-1## are both even, i.e. ##4\,|\,(a^2-1)(a^2+1)=a^4-1## or ##a^4\equiv 1\pmod{4}.##
 
  • Like
Likes Math100
  • #3
fresh_42 said:
The modulo ##2## case is a bit messy.

We have ##a\equiv 1\pmod{2}## so ##a^2\equiv 1\pmod{2}##. But then, ##a^2+1## and ##a^2-1## are both even, i.e. ##4\,|\,(a^2-1)(a^2+1)=a^4-1## or ##a^4\equiv 1\pmod{4}.##
I agree, since ## a ## is odd.
 
  • Like
Likes fresh_42

FAQ: Show that ## 60 ## divides ## a^{4}+59 ##

1. How do you prove that 60 divides a^4 + 59?

To prove that 60 divides a^4 + 59, we need to show that there exists an integer k such that a^4 + 59 = 60k. This can be done through mathematical induction or by using the properties of divisibility.

2. What is the significance of 60 in this problem?

The number 60 is significant because it is the least common multiple of 4 and 15, the exponents of a and 59 respectively. This means that any number that is divisible by both 4 and 15 is also divisible by 60.

3. Can you provide an example to illustrate the divisibility of 60 in this problem?

Sure. Let's take a = 2. Then a^4 + 59 = 2^4 + 59 = 75. We can see that 75 is divisible by 15 (since 75 = 5 x 15) and 4 (since 75 = 4 x 18 + 3). Therefore, 75 is also divisible by 60.

4. Is it possible for a^4 + 59 to be divisible by 60 if a is not an integer?

No, it is not possible. The problem states that a must be an integer, and if a is not an integer, then a^4 will not be an integer either. Therefore, a^4 + 59 will not be divisible by 60.

5. Can this problem be solved using other methods besides mathematical induction?

Yes, there are other methods that can be used to prove the divisibility of 60 in this problem. For example, we can use the fact that if a number is divisible by both 4 and 15, then it is also divisible by their product (60). We can also use the properties of congruence to show that a^4 + 59 is congruent to 0 (mod 60).

Similar threads

Back
Top