Divisibility Proof: Prove n^7 - n Divisible by 7

AI Thread Summary
The discussion focuses on proving that for any positive integer n, the expression n^7 - n is divisible by 7. Participants suggest breaking the proof into seven cases based on the possible remainders when n is divided by 7. The hint of using Fermat's Little Theorem is mentioned, along with the idea of using proof by exhaustion. One user expresses difficulty in concluding the proof despite understanding the approach. The consensus is that the proof must adhere to the structure of analyzing the seven cases.
tysonk
Messages
33
Reaction score
0
Can someone help me with the following proof.
prove that if n is a positive integer then n^7 - n is divisible by 7. This should be done by breaking it down into 7 cases.
 
Physics news on Phys.org
welcome to pf!

hi tysonk! welcome to pf! :wink:

(try using the X2 icon just above the Reply box :smile:)
tysonk said:
Can someone help me with the following proof.
prove that if n is a positive integer then n^7 - n is divisible by 7. This should be done by breaking it down into 7 cases.

hint: what do you think the 7 cases might be? :wink:
 
tysonk said:
Can someone help me with the following proof.
prove that if n is a positive integer then n^7 - n is divisible by 7. This should be done by breaking it down into 7 cases.

n x 2n x 3n x 4n x ... x 6n == 6! (mod 7) in some permuatation.
6! x n^6 == 6! (mod 7)
n^7 / n == 1 (mod 7)

now you can draw conclusion.. or refer to generalised theorem- fermat's little theorem.
 
"Should be done" or "Must be done" by breaking into cases of 7's? Would proof using mathematical induction be acceptable for you?
 
It should be done using the 7 cases.
I know the 7 cases are the remainders. 0, 1, 2, 3, 4, 5, 6 and using proof by exhaustion for the 7 cases. (and perhaps factoring the original)
However, I'm still not able to draw a conclusion. The help is appreciated.
 
tysonk said:
It should be done using the 7 cases.
I know the 7 cases are the remainders. 0, 1, 2, 3, 4, 5, 6 and using proof by exhaustion for the 7 cases. (and perhaps factoring the original)
However, I'm still not able to draw a conclusion. The help is appreciated.

ok, take remainder 3, so n = 7k + 3 …

then n7 - n = (7k + 3)7 - (7k + 3) = … ? :wink:
 

Thread 'Finding the number of ways to arrange identical balls in a circle (3 different colors)'

I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense. Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities? Thanks
View full post »

Similar threads

Prove: If the integer ## a ## is not divisible by ## 2 ## or ## 3 ##....
Replies
9
Views
2K
Prove that ## a^{3}+1 ## is divisible by ## 7 ##.
Replies
1
Views
1K
Proof That an Integer is Divisible by 2
Replies
3
Views
2K
Prove that the integer ## 53^{103}+103^{53} ## is divisible by....
Replies
1
Views
2K
Divisibility of Integers ## 176521221 ## & ## 149235678 ## by 9 & 11
Replies
9
Views
2K
Proof: Divisibility of Integers by 4
Replies
5
Views
2K
Basic counting methods — integers between 1 and 100 that are divisible by 7
Replies
19
Views
2K
Proof: Integer Divisibility by 3 via Polynomials
Replies
2
Views
2K
Prove that ## 7, 11 ##, and ## 13 ## all divide ## N ##
Replies
6
Views
2K
Verify that ## N-M ## is divisible by ## 9 ##
Replies
7
Views
2K

Hot Threads

Recent Insights

Back
Top