What is the minimum value of n such that there exist integers a 1 , a 2 , … , a n that satisfy
a 1 5 + a 2 5 + ⋯ + a n 5 = 2 8 ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
For problems like this where we think there is a solution involving "consider the equation with a suitable modulus n , " most people think it is blind trial and error. They calculate all possible values of x k ( m o d n ) , and try to substitute it into the equation. Each additional value and term increases the complexity. However, with some forethought we can keep our complexity low.
Euler's Totient Theorem is a generalization of Fermat's Little Theorem which states
a ϕ ( n ) ≡ a ( m o d n )
where a is any integer relatively prime to n.
By assuring ϕ ( n ) = k or ϕ ( n ) = 2 k , we know
a k ≡ a ( m o d n )
or
a 2 k ≡ a ( m o d n )
This allows for the very convienent modulo results of -1, 0, or 1, which makes the problem much easier to handle.
Good solution!
Beautiful!
NICE SOLUTION
This is beautiful!
Can u explain why u were looking for such n s ( rule of thumbs)
Log in to reply
The numbers which satisfy that condition give nice mods to work with.
What does the Greek represent?
Log in to reply
The Euler Totient Function. ϕ ( k ) outputs the number of positive integers less than k that are co-prime to k .
Does anyone know of a solution for n=5 other than 2, -1, -1, -1, -1?
Doesn't allowing different subscripted values of a to have the same value violate a convention? The solution where a1 = 2 and a2, a3, a4, and a5 are all -1 was immediately obvious to me, but I thought that it violated a convention that different subscripts of a variable are assumed to have unique values. But then I convinced myself that the problem has no other solution.
Log in to reply
No, there is no convention specifying that apart from in cryptarithms. In normal algebra, you could use different variables that could stand for the same value.
Considering negative integers allowed, and since and odd power like 5 of a negative integer renders the sign negative, i.e., (-1)^5=-1. We need 28=32-4=2^5-1-1-1-1=2^5+4×(-1)^5, that is 5 integers.
That only shows it is possible for 5 integers. How do you know it isn't possible for 4 integers?
For this type better consider a least +integer like 2 then a -integer -1 substitute you'll get least 'n' value
This is not rigorous nor correct reasoning. What if there are larger positive integers with smaller negative integers that work better?
Problem Loading...
Note Loading...
Set Loading...
We want to use a good mod to try to prove this. A rule of thumb for powers of k is to use a mod n such that ϕ ( n ) = k or ϕ ( n ) = 2 k . After some working, we should find that n = 1 1 satisfies. Let's use this.
By Fermat's Little Theorem , x 1 0 ≡ 0 , 1 ( m o d 1 1 ) . Thus, x 5 ≡ 0 , ± 1 ( m o d 1 1 ) . Thus, we have
a 1 5 + a 2 5 + … + a n 5 ≡ m 1 + m 2 + … + m n ( m o d 1 1 ) , m i ∈ { 0 , ± 1 } ≡ 2 8 ( m o d 1 1 ) ≡ − 5 ( m o d 1 1 )
Thus, n must be at least 5 for this to occur. In fact, we find that n = 5 does work if we have a 1 = 2 , a 2 = a 3 = a 4 = a 5 = − 1 . Thus, n ≥ 5 .