(Answers Dev) Restored edit
Info
This question is locked. Öffnen Sie sie erneut, um sie zu bearbeiten oder zu beantworten.
Check the result if it is divisible or not
3 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
stealgirlfriend
am 17 Apr. 2024
Locked: John D'Errico
am 10 Jun. 2024
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
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?
1 Kommentar
Akzeptierte Antwort
John D'Errico
am 17 Apr. 2024
Bearbeitet: John D'Errico
am 17 Apr. 2024
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)
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.
3 Kommentare
John D'Errico
am 17 Apr. 2024
Sigh. What does
sym(4)^2026
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
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
am 10 Jun. 2024
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)
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.
Weitere Antworten (0)
This question is locked.
Siehe auch
Kategorien
Mehr zu Number Theory finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!