Check the result if it is divisible or not

N = 2026;
S = 4^N + 7^N;
if mod (S,5) == 0;
   disp(sprintf('S(2026) is divisible by 5'));
else
   disp(sprintf('S(2026) is not divisible by 5'));
end

S(2026) is not divisible by 5

The result is S(2026) is not divisible by 5, but it actually can be divisible by 5. The reason is S(2026) = inf., that's why it can't give me the proper answer. So how can i get the exact integer number of S or is it another way to check and get correct answer?

[Rena Berman]

(Answers Dev) Restored edit

Answer 1

[John D'Errico]

Do you understand that you are using DOUBLE precision arithmetic to compute that mod? Do you understand that 7^2026 is a number with roughly 1700 decimal digits?

2026*log10(7)

ans = 1.7122e+03

So hoping to compute that modulus using double precision arithmetic, which will effectively require computing the least significant digit of a number with 1700 and more digits is a silly thing? Not to mention that it will overflow (as you clearly found.) The point is, this assignment was given to you to explicitly force you to think about how you might achieve the result, WITHOUT trying to compute that number via brute force. Actually, you are lucky, had I given out the assignment, I'd have made the exponent MUCH MUCH larger, so that even trying to compute those powers using syms directly would have been difficult. Your teacher was being nice. ;-)

You could use syms though, as a hint.

Even better would be to use powermod. Since this is your homework assignment, I'll stop here.

And, of course, a little creative thinking and some mathematics would allow you to determine that result in a very pretty way, without even resorting to either approach. Would a binomial expansion help you? Again though, since it is homework ... this is your task to solve. As it is, I've already told you two direct ways to accomplish the task.

[stealgirlfriend]

I manage to solve every tasks but can not for this one. It might be i forgot it is not only about how to code in Matlab to get the answer. I appreciate it, thank you so much

[John D'Errico]

Sigh. What does

sym(4)^2026

ans = 

59366634639738578396858924333891103661924503799547425182040199347508968683743970407751181251967270687878800954106240103441653754895571274077112553178003808963351103588121873050361136286845960416623487959205701044219058464898223107051781805941151709333599223367957830764185248923474694556402254067029277223735274388723257049261229987575362710037983302608655746399962634793783935550435012366262652423170825134086799805931959662895820698286559711086709766908608630805531926004145764958839996015230609150891584179702455024278829854166235510651699092467973557132911451665584543522426542853077782228005082497162004222958774250054900995270698549312560749548430455562890853014000252245391380181172023928861656055424321344567305460197255748395263185018018226148330670134034285984545492333625122202809608492903153917101532401208112043263309544847911831521274898417939346928017866143529762612761922035653857183284607745344085068207204377748464635854355718260068298705134181082614034781948919089477999447649482057432676268141873132393026158358138281950753341266566179788615712958136150798101170966984739291145082058328293236688660495576898653203974105147614359685002398311008475229171305796654195951964704862674468213077161852010496

do? This is the simplest thing you could try, but it will give you the result. Again, I said your teacher was being nice. Were it me assigning the problem, these numbers would have Avogadro's number of digits.

Better yet, is to learn to use powermod.

help sym/powermod

 POWERMOD Modular power
    B = POWERMOD(A, N, M) computes MOD(A.^N, M)
 
    Examples:
       powermod(2, 100, 101)
       ans =
           1
 
    See also MOD.

Finally, consider if this is always true?

4^n == (5-1)^n

Does that help you in any way? Think about a binomial expansion now. What does thta tell you in terms of mod 5 arithmetic? Admittedly,

7^n = (5+2)^n

is a little more complicated, but it gets you much closer to an answer. You can now prove a nice result using mathematical induction.

All of those ideas will give you the answer. Take a shot at it. If you can at least come close, show what you tried, and I will see if I can help you more.

[John D'Errico]

Long since a done question. But now I'll add how I would have solved the problem. Note that no need for MATLAB is even necessary. Pencil and paper is entirely adequate.

The question was if the number 4^n + 7^n is divisible by 5, for n = 2026. And of course this will fail miserably using doubles. And even using syms, the numbers get pretty large. It is doable though using brute force. But of course, the direct approach is to use powermod, and that was my suggestion, though I did not write this line of code at the time:

powermod(4,2026,5) + powermod(7,2026,5)

ans = 5

At the time, I offered, that if the OP was willing to make some effort on it, I would explain up a moderately pretty way to solve it. Nothing happened. Even so, the solution is actually pretty nice. All you need do is rewrite the expression of interest as:

4^n + 7^n == (5-1)^n + (5+2)^n

Taken modulo 5, if you expand the pair of binomials on the right, all but the last term would drop out since every other term must be a multiple of 5. Think about that claim! Convince yourself it is true. Now we have

mod(4^n + 7^n,5) = mod((-1)^n,5) + mod((2)^n,5)

Since clearly (-1)^n is always 1 for even n, and -1 for odd n, all we need do is consider the 2^n term. And there we can use Fermat's little theorem, which would tell us that

mod(2^(5-1),5) == 1

since 2 and 5 are co-prime. From there, we can show that

mod(2^(4*n),5) == 1

since 1 to any power is still just 1.

and also that successive powers of 2 will follow the repeating pattern {1 2 4 3 ... }. Now we can combine the two patterns, to see they will be

[1, -1, 1, -1, ...] + [1, 2, 4, 3, ...] = [2, 1, 5, 2, ...]

Only in the third case, thus for numbers of the form 4*k+2, will we ever have:

mod(4^n + 7^n , 5) == 0

Again, ONLY for n of the general form 4*k+2. Since 2026 is of that form, we see the desired sum is indeed a multiple of 5. No computation need be done at all, beyond seeing that 2026 is 2 more than a multiple of 4.

The nice thing about this solution is even had n been some immensely huge number, the above method would still work. It is kind of a pretty solution, since it relies on binomial expansions. It even employs Fermat's little theorem, and any time you can invoke Fermat on a homework assignment, it adds some fun.

Again, a pretty way to solve the problem. And I never even needed to use MATLAB.