{"id":1336,"date":"2021-03-12T10:05:12","date_gmt":"2021-03-12T17:05:12","guid":{"rendered":"http:\/\/www.davidgunter.com\/?p=1336"},"modified":"2022-03-13T17:57:20","modified_gmt":"2022-03-14T00:57:20","slug":"an-interesting-calculator-discovery-and-the-result-of-a-12-hour-drive","status":"publish","type":"post","link":"https:\/\/www.davidgunter.com\/es-mx\/2021\/03\/12\/an-interesting-calculator-discovery-and-the-result-of-a-12-hour-drive\/","title":{"rendered":"An interesting calculator discovery and the result of a 12-hour drive"},"content":{"rendered":"\n

I recently drove 12 hours from our home in Santa Fe to our beach spot in Mexico while Sonya had numerous virtual meetings and phone calls en route. This meant that I was not able to listen to music nor any of my podcasts as I do not like to drive with earphones in use. No matter, I had come across something interesting a few days prior and I spent most of the entire drive focused on it. I wrote a draft of this post in my notebook the next morning so I wouldn’t forget it.<\/p>\n\n\n

\"Rendered
\nA few days prior I was working on something and noticed the following. Suppose you started with the number 2 and then squared it. You get the number 4. Squared again, 8. Then 16, then 32, and so on. What I noticed was the last digit of each subsequent squaring, written down as {2, 4, 8, 6, 2}. After five such squares, that is after reaching \"2^5\", we end up back at 2. From there the cycle repeats. Here are the various powers of 2 and the last digit of each<\/p>\n

\"Rendered<\/p>\n

This is not unique to the number 2. Any number raised to increasing integer powers will show a cycle. What is interesting is that there will never be a cycle length larger than 5 when looking at the frequency of occurrence of the last digit. Shown in the next table are the various cycles that may appear.<\/p>\n

\"Rendered<\/p>\n

We see that not all cycles are of length 5. For 1, 5, and 6, in fact, the cycle length is only 1. The numbers 4 and 9 have cycles of length 2. But there is no cycle greater than length five. Why is that? And why is it that no matter what the starting number is, we will reach the same last digit after raising any number to a fifth power?<\/p>\n

This applies to numbers of more than a single digit, of course. Suppose we started with the number 83. In successive powers we have 83, \"\,\" 6,889, \"\,\" 571,787, \"\,\" 47,458,321, and 3,939,040,643. The cycle of last digits is {3, 9, 7, 1, 3}, the same as for the digit 3, itself. No matter how large of a number we start with, after raising it to successive powers the last digit will cycle back around to the last digit of the number with which we started, following one of the cycles appearing in the table above for single digits. If it is not clear why this is so, think about what a multiple digit number is. It is a single digit, plus another digit multiplied by 10, plus another digit multiplied by 100, and so on. Consider a two-digit number \"10y + x\" where \"x\" and \"y\" are single digits. Squaring it gives<\/p>\n

  <\/span>   <\/span>\"\begin{equation*} <\/p>\n

The first two terms on the right end in 0 so the last digit will be determined by the last digit of \"x^2\".<\/p>\n

Thus the questions remain, why are there no cycles greater than 5 and why, no matter what, when we raise any number to the power of 5 do we get a number whose last digit is the same as the number with which we began?<\/p>\n

\"Rendered
\nWhen talking about cycles that appear in numbers there is a good chance that we will be making use of modular arithmetic<\/a>, a part of mathematics based on wrap-around<\/em> behavior. If you are unfamiliar with this subject, think of how most Americans keep time using a 12-hour clock. Let \"n\" represent the number of hours that have passed since midnight. We would say that the current hour is \"n\" mod 12, that is, it is the reminder after dividing by 12. If n = 6 then 12 goes into 6 zero times, with a remainder of 6. So it is 6 AM. If n = 14 then 12 goes into 14 once with a remainder of 2. It’s 2 PM. We say the hour of the day is based on a modular-12 system.<\/p>\n

Modular arithmetic will come into play in our explanation for the questions raised at the end of the last section. We will use the concept of congruence between numbers based on some modular value. Two values \"a\" and \"b\" are said to be congruent based on some modular value \"m\" if the difference between the two values is evenly divisible by \"m\". This is written as <\/p>\n

  <\/span>   <\/span>\"\[ a \equiv b \pmod{m}. \]\"<\/p>\n

Note the three-lined equivalence symbol being used and the ‘(mod m)’. The parentheses around the latter indicate that it applies to the whole equation, both the left and right sides. The notation is not too complicated and means nothing more than the difference \"a-b\" is evenly divisible by \"m\", i.e. \"a-b = km\" for some integer \"k\". Another way mathematicians write “is evenly divisible by” is the following notation,<\/p>\n

  <\/span>   <\/span>\"\[ m|(a-b) .\]\"<\/p>\n

Keep in mind the ‘(mod m)’ type of notation in what follows. A common temptation is to think that the statement \"a \equiv b \pmod{m}\" is a shorthand way to say, “\"b\" is the remainder when \"a\" is divided by \"m\".” However, this is not always the case. Here are a few examples to drive home the meaning of the congruence relation.<\/p>\n

  <\/span>   <\/span>\"\[ 12 \equiv 8 \pmod{4},\t \]\"<\/p>\n

because \"12-8=4\" is evenly divisible by 4. Note that \"8\" is definitely not the remainder of \"12 \div 4\".<\/p>\n

  <\/span>   <\/span>\"\[ 33 \equiv 1 \pmod{16},\t \]\"<\/p>\n

because \"33-1=32\" is evenly divisible by 16.<\/p>\n

\"Rendered
\nAn interesting theorem involving modular arithmetic and prime numbers was introduced by Fermat and is known as Fermat’s Little Theorem<\/em> in deference to his more famous Last Theorem<\/em>.<\/p>\n

Recall that a prime number is one that is only divisible by itself and the number 1. Fermat’s Little Theorem states that for any prime number \"p\" and any number \"a\" not divisible by \"p\" that<\/p>\n

  <\/span>   <\/span>\"\[ a^{p-1} \equiv 1 \pmod{p}. \]\"<\/p>\n

This theorem is essential to answering our questions so it is worth showing a proof. Also, it leads to a generalization due to Euler that will more directly answer our questions.<\/p>\n

To prove Fermat’s Little Theorem, start by creating a set of numbers from 1 to \"p-1\". Call this set \"S\",<\/p>\n

  <\/span>   <\/span>\"\[ S = \{ 1, 2, 3, \ldots p-1\}.\]\"<\/p>\n

There are a total of \"p-1\" elements of \"S\", all less than \"p\", and so it should be obvious that for any member \"n\" of \"S\", written as \"n \in S\", that \"n\" mod \"p\" = \"n\". So every member of \"S\" is unique and every member has a unique congruence modulo \"p\", that is, a unique remainder mod \"p\", namely itself. Next form a new set \"a \cdot S\" where we multiply every member of \"S\" by \"a\". This new set is<\/p>\n

  <\/span>   <\/span>\"\[ a \cdot S = \{ a, 2a, 3a, \ldots (p-1)a \}.\]\"<\/p>\n

Every element of this new set also has a unique congruence modulo \"p\". To show this, assume that two members of \"a\cdot S\" had the same congruence relationship modulo \"p\". That is, <\/p>\n

  <\/span>   <\/span>\"\[ na \equiv ma \equiv q \pmod{p}\]\"<\/p>\n

for some integer q. This implies that \"na = kp + q\" and \"ma = k^{'}p + q\" for integers \"k, k^{'}\". If we subtract these we get<\/p>\n

  <\/span>   <\/span>\"\[ na - ma = (k-k^{'})p. \]\"<\/p>\n

The right-hand side is clearly divisible by p and this means that<\/p>\n

  <\/span>   <\/span>\"\[(n-m) a \equiv 0 \pmod{p}. \]\"<\/p>\n

The integers \"n\" and \"m\" are both less than \"p\" because of how the set \"S\" was constructed, hence their difference must also be less than \"p\". This fact, combined with the assertion at the beginning that \"a\" is not divisible by \"p\", means that the only way the above congruence relation can hold true is if \"n = m\", proving the congruence uniqueness for the set \"a \cdot S\".<\/p>\n

We have just shown that all of the congruences of the set \"a\cdot S\" are unique. Each one is also less than \"p\" by definition of taking the modulus with \"p\", so there is a one-to-one correspondence with the congruences of the set \"S\" with those of the set \"a\cdot S\". The congruences modulo \"p\" of the set \"a \cdot S\" are a permutation of those of \"S\". However, we can multiply all these congruences to see that<\/p>\n

  <\/span>   <\/span>\"\[ 1\cdot 2\cdot3\cdots (p-1) \equiv a\cdot 2a \cdot 3a \cdots (p-1)a \pmod{p},\]\"<\/p>\n

  <\/span>   <\/span>\"\[ (p-1)! \equiv (p-1)! \, a^{p-1} \pmod{p},\]\"<\/p>\n

and finally, we can divide each side by \"(p-1)!\" to get the result, Fermat’s Little Theorem,<\/p>\n

  <\/span>   <\/span>\"\[ a^{p-1} \equiv 1 \pmod{p}.\]\"<\/p>\n

\"Rendered
\nEuler extended Fermat’s Little Theorem to non-prime values of \"p\". Suppose \"m\" is any integer and that \"a\" and \"m\" are coprime. This just means that the greatest common divisor of either number is 1, written gcd(\"a,m\") = 1. Then in general Fermat’s Little Theorem does not hold. We already see a problem with the set \"S = \{1, 2, 3, \ldots (m-1)\}\". Some of those elements may have the same congruence relations modulo \"m\". Instead, we form a new set containing only the numbers 1 to \"m-1\" that are coprime to \"m\". For example, if \"m=12\" our set would look like this,<\/p>\n

  <\/span>   <\/span>\"\[S = \{ 1,5,7,11\}. \]\"<\/p>\n

Those are the only numbers in the range 1 to 12 that are coprime to 12. (Numbers are not considered coprime to themselves.) The number of elements of \"S\" is denoted \"\phi(m)\" and is called Euler’s totient function. \"\phi(m)\" is the count of numbers less than \"m\" that are coprime to \"m\". There is no general function to write down in order to compute \"\phi(m)\" but it has been tabulated for numerous values in various tables. Here we show just a few examples.<\/p>\n

  <\/span>   <\/span>\"\begin{eqnarray*}<\/p>\n

Note in particular the last row. For any prime number \"p\" we have \"\phi(p) = p-1\" and you should see that Fermat’s Little Theorem is just a special case of Euler’s Theorem when \"m\" is a prime number. Another property of the totient function is that for any two prime numbers \"p\" and \"q\", \"\phi(pq) = \phi(p) \phi(q)\".<\/p>\n

Let’s return to the new set \"S = \{n_1, n_2, n_3, \ldots, n_{\phi(m)} \}\". As for the case in proving Fermat’s Little Theorem, each of these numbers \"n_i\" is less than \"m\" and the congruences are all unique. Again we form a new set \"a\cdot S\" where we multiply each member of \"S\" by the number \"a\".<\/p>\n

  <\/span>   <\/span>\"\[ a \cdot S = \{an_1, an_2, an_3, \ldots, an_{\phi(m)} \}.\]\"<\/p>\n

If \"a n_i \equiv k \pmod{m}\" and \"a n_j \equiv k \pmod{m}\" for some \"i, j\" then this implies that \"m\" divides \"(n_i - n_j) a\", but \"a\" and \"m\" are coprime so we know \"m\" does not divide \"a\". Thus \"m\" can only divide \"n_i - n_j\" which can only happen if \"i=j\". Therefore, the set \"a\cdot S\" is a permutation of all the congruences contained in \"S\" modulo \"m\", just as what we found for the sets used to prove Fermat’s Little Theorem. As before, we now multiply all the congruences to see that<\/p>\n

  <\/span>   <\/span>\"\[ (n_1 \cdot n_2 \cdot n_3 \cdots n_{\phi(m)}) \equiv (n_1a \cdot n_2a \cdot n_3a \cdots n_{\phi(m)}a) \pmod{m},\]\"<\/p>\n

  <\/span>   <\/span>\"\[ (n_1 \cdot n_2 \cdot n_3 \cdots n_{\phi(m)}) \equiv (n_1 \cdot n_2 \cdot n_3 \cdots n_{\phi(m)}) a^{\phi(m)} \pmod{m},\]\"<\/p>\n

and upon dividing each side by the \"n_i\" multiplication terms, we arrive at Euler’s Theorem for numbers \"a\" and \"m\" coprime,<\/p>\n

  <\/span>   <\/span>\"\[ a^{\phi(m)} \equiv 1 \pmod{m}. \]\"<\/p>\n

As a corollary we can multiply both sides by \"a\" to get the relationship<\/p>\n

  <\/span>   <\/span>\"\[ a^{\phi(m)+1} \equiv a \pmod{m}. \]\"<\/p>\n

\"Rendered
\nSo how does Euler’s Theorem help answer the question of why there is no cycle length greater than 5 for examining the last digit when raising numbers to successive powers? We’re getting there.<\/p>\n

Suppose \"m=\alpha \beta\" where both \"\alpha\" and \"\beta\" are prime numbers and neither one divides \"a\". Then we will claim that<\/p>\n

  <\/span>   <\/span>\"\[ a^{\phi(\alpha \beta)+1} = a \pmod{\alpha\beta} \]\"<\/p>\n

holds for all values of \"a\", not just those coprime to \"\alpha\beta\". <\/p>\n

If \"a = \alpha\beta\" then it is obviously true. If \"a\" is not a multiple of either \"\alpha\" or \"\beta\" then it is true by Euler’s Theorem. All that is left is to consider the case where \"a\" is a multiple of either \"\alpha\" or \"\beta\". Suppose \"a = k\alpha\" for some integer \"k\". Then<\/p>\n

  <\/span>   <\/span>\"\[ (k\alpha)^{\phi(\alpha\beta) + 1} \equiv k\alpha \pmod{\alpha\beta} \]\"<\/p>\n

means that <\/p>\n

  <\/span>   <\/span>\"\[ \alpha\beta \left| \left[ (k\alpha)^{\phi(\alpha\beta) + 1} - k\alpha \right] \right., \]\"<\/p>\n

i.e. that \"\alpha\beta\" divides the terms in brackets. We can clearly divide \"k\alpha\" from both terms in the brackets so all that is left is to show the \"\beta\" divides the terms<\/p>\n

  <\/span>   <\/span>\"\[ (k\alpha)^{\phi(\alpha\beta) } - 1 \]\"<\/p>\n

Note that that by our assumptions (\"\alpha\" and \"\beta\" both prime numbers) that \"\gcd{(k,\alpha)} = 1\", and \"\gcd{(\alpha, \beta)} = 1\". By Euler’s Theorem we have that<\/p>\n

  <\/span>   <\/span>\"\[ \beta \left| \left[ (k\alpha)^{\phi(\beta)} - 1 \right] \right. \]\"<\/p>\n

or<\/p>\n

  <\/span>   <\/span>\"\[ (k\alpha)^{\phi(\beta)} \equiv 1 \pmod{\beta}. \]\"<\/p>\n

By the multiplicative property of modular arithmetic (see appendix) we can raise the power of \"(k\alpha)^{\phi(\beta)}\" and the congruence relation will still hold, so<\/p>\n

  <\/span>   <\/span>\"\[ \left[ (k\alpha)^{\phi(\beta)}\right]^{\phi(\alpha)} = (k\alpha)^{\phi(\beta)\phi(\alpha)} = (k\alpha)^{\phi(\alpha\beta)} \equiv 1 \pmod{\beta}, \]\"<\/p>\n

where we made use of the fact that \"\phi(\alpha\beta) = \phi(\alpha)\phi(\beta)\" for prime numbers.<\/p>\n

To restate, for any<\/em> number \"a\" and \"m=\alpha\beta\" where \"\alpha\" and \"\beta\" are both prime, <\/p>\n

  <\/span>   <\/span>\"\[ a^{\phi(m)} \equiv 1 \pmod{m}.\]\"<\/p>\n

\"Rendered
\nFinally, to address our questions let \"\alpha=2\" and \"\beta = 5\", so that \"m=10\". We know that \"\phi(10) = 4\" from the previous chart. By Euler’s Theorem then, for any<\/em> number \"a\",<\/p>\n

  <\/span>   <\/span>\"\[ a^4 \equiv 1 \pmod{10},\]\"<\/p>\n

and<\/p>\n

  <\/span>   <\/span>\"\[ a^5 \equiv a \pmod{10}.\]\"<\/p>\n

The fact that \"a^5 - a\" is evenly divisible by 10 means that any number that has been raised to the fifth power ends in a digit that is the same as the last digit of \"a\", answering one of our questions. We also know from earlier discussions that once a number ends in the same digit as the last digit of the number with which we began, that the cycle starts again. There can be no cycle of length greater than 5.<\/p>\n

\"Rendered
\nThe multiplicative property of modular arithmetic states that if \"a_1 = b_1 \pmod{m}\" and \"a_2 = b_2 \pmod{m}\" then <\/p>\n

  <\/span>   <\/span>\"\[ a_1 a_2 = b_1 b2 \pmod{m}. \]\"<\/p>\n

To see this, note that \"a_1 = k_1 m + b_1\", \"a_2 = k_2 m + b_2\". Then<\/p>\n

  <\/span>   <\/span>\"\begin{eqnarray*}<\/p>\n","protected":false},"excerpt":{"rendered":"

I recently drove 12 hours from our home in Santa Fe to our beach spot in Mexico while Sonya had numerous virtual meetings and phone calls en route. This meant that I was not...<\/p>\n","protected":false},"author":1,"featured_media":1468,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[159],"tags":[162,161,163,160,164],"class_list":["post-1336","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-mathematics","tag-eulers-theorom","tag-fermats-little-theorem","tag-fifth-powers","tag-mathematics","tag-modular-arithmetic"],"_links":{"self":[{"href":"https:\/\/www.davidgunter.com\/es-mx\/wp-json\/wp\/v2\/posts\/1336","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.davidgunter.com\/es-mx\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.davidgunter.com\/es-mx\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.davidgunter.com\/es-mx\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.davidgunter.com\/es-mx\/wp-json\/wp\/v2\/comments?post=1336"}],"version-history":[{"count":5,"href":"https:\/\/www.davidgunter.com\/es-mx\/wp-json\/wp\/v2\/posts\/1336\/revisions"}],"predecessor-version":[{"id":1469,"href":"https:\/\/www.davidgunter.com\/es-mx\/wp-json\/wp\/v2\/posts\/1336\/revisions\/1469"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.davidgunter.com\/es-mx\/wp-json\/wp\/v2\/media\/1468"}],"wp:attachment":[{"href":"https:\/\/www.davidgunter.com\/es-mx\/wp-json\/wp\/v2\/media?parent=1336"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.davidgunter.com\/es-mx\/wp-json\/wp\/v2\/categories?post=1336"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.davidgunter.com\/es-mx\/wp-json\/wp\/v2\/tags?post=1336"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}