Mathematics desk
< August 1	<< Jul \| August \| Sep >>	August 3 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 2

Problem Solving 2

Hello. Thank you for affirming my solution yesterday, I'm very grateful. I now have a question to ask.

Another problem I solved was

Is $3^{444}+4^{333}\,\!$ divisible by 5?

I solved this via modulo 5 arithmetic

$(3^{4})^{111}+(4^{3})^{111}\,\!$

$\implies 81^{111}+64^{111}\,\!$

$81\equiv 1{\text{ (mod }}5)$

$64\equiv -1{\text{ (mod }}5)$

$\implies 1^{111}-1^{111}$

$\implies 0$

After doing this I noticed that if I had used modulo five arithmetic on the powers, I would have ended up with

$3^{4}+4^{3}\,\!$

And then I could have simplified this and used modulo five arithmetic on the numbers, which would have been basicaly the same way of solving it as before.

Does this always work? 172.142.215.130 14:22, 2 August 2007 (UTC)[reply]

You got lucky, this time --

3^{9}+4^{8}\,\!\equiv 4{\text{ (mod }}5)

However, it is modding the exponents by 4 that would do the trick, because of a number theory thing called Totient function and the Chinese remainder theorem. The articles may interest you, though they're a bit abstract. Gscshoyru 14:37, 2 August 2007 (UTC)[reply]

So what are you saying? That modding exponents by 4 will always work when modding them by 5 won't? 172.142.215.130 15:45, 2 August 2007 (UTC)[reply]

No. When trying to find x^y mod 5 then modding the exponent by 4 will give you the same number, i.e. x^y is congruent to x^(y-4) mod 5. 5 is prime, so the totient of 5 is 4. In the case of say, 15, the totient of 15 is 2 * 4 = 8, so x^y is congruent to x^(y-8) mod 15. 4 works when modding by 5, but the number you can mod the exponent by depends on the number you're modding by. Understand? Gscshoyru 15:50, 2 August 2007 (UTC)[reply]

I think so. But I don't quite see how you find the totient of a number. Do you find its prime factors, subtract one from each and multiply them together? e.g. totient of 14 is (2-1) times (7-1) which is 6. 172.142.215.130 16:04, 2 August 2007 (UTC)[reply]

Not exactly. If there's more than one of the same prime, like 675 = 3^3 * 5 ^ 2, for instance, then you multiply each (p-1) by p ^ (n-1), where n is the number of times p goes into the number, so for 675 we have (3-1) * 3 ^ 2 * (5- 1) * 5^1 = 360. For 14, we have (2-1) * 2 ^ 0 * (7-1) * 7 ^ 0 = 14. The formula is in the article: Totient function. Ok? Gscshoyru 16:19, 2 August 2007 (UTC)[reply]

I mentioned the homomorphism of arithmetic in examining the previous proof, but without precise details. Now we'd better look more carefully. (Incidentally, we are following in the footsteps of Gauss, who developed these ideas and put them to good use in number theory.)

Modulo arithmetic with a modulus m means the same as doing ordinary integer arithmetic, but treating numbers that differ by an integer multiple of m as equivalent. The arithmetic in question consists of addition, subtraction, and multiplication. The homomorphism is thus a mapping from the ring Z (the integers) to the ring Z/mZ (the integers modulo m).

{\begin{aligned}h\colon \mathbb {Z} &{}\to \mathbb {Z} /m\mathbb {Z} \\n&{}\mapsto n{\pmod {m}}\end{aligned}}

We call this mapping a (ring) homomorphism because it preserves the structure of (ring) arithmetic.

{\begin{aligned}h(a+b)&{}\equiv h(a)+h(b){\pmod {m}}\\h(a-b)&{}\equiv h(a)-h(b){\pmod {m}}\\h(a\times b)&{}\equiv h(a)\times h(b){\pmod {m}}\end{aligned}}

Proving these three items is not so hard, and may help make the relationship more memorable. For example, let

{\begin{aligned}a&{}=\kappa m+a',\\b&{}=\lambda m+b'.\\\end{aligned}}

Then when we add a and b we find

{\begin{aligned}a+b&{}=(\kappa m+a')+(\lambda m+b')\\&{}=(\kappa +\lambda )m+(a'+b')\end{aligned}}

Thus it is safe to reduce before adding, though we may need to reduce again after adding.

What can we say about powers? From the three known facts, we can easily deduce that

h\left(a^{n}\right)\equiv \left(h(a)\right)^{n}{\pmod {m}};

but notice that the power n is not reduced. In fact, it is easy to give examples, like 2⁵ (mod 4), where reducing the power doesn't work. Of particular relevance is Fermat's little theorem, which tells us that for a prime modulus, p, we have

a^{p}\equiv a{\pmod {p}}\,\!

for any integer a; reducing the exponent would give a power of zero, not one. (This is a beautiful theorem; see here for several proofs.)

To summarize, your first approach is correct, but the approach of reducing the exponents is not reliable. --KSmrq^T 19:41, 2 August 2007 (UTC)[reply]

Holdon a second... what? You can reduce the exponents, not by the number you're modding by, but by the totient of it, right? I'm pretty sure I'm right about that... RSA is based on it, among other things. Gscshoyru 19:54, 2 August 2007 (UTC)[reply]

See Fermat-Euler theorem. As KSmrq's 2^5 mod 4 example shows, we can only reduce the exponent by the totient of the modulus if a (in this case 2) is coprime to n (here 4). Algebraist 20:43, 2 August 2007 (UTC)[reply]

The problem here is that in answer to a previous question I mentioned that the homomorphism allowed reduction, but did not state specifics. Not knowing the details, it is quite natural to try reducing the power in exactly the same way as terms in a sum. As we see, that does not work. Gscshoyru is trying to say that we can reduce the power by an amended rule, using the totient of the modulus rather than the modulus itself. As we see, that can also fail.

Fermat's little theorem provides one way to reduce an exponent sometimes, but not in the way used in the poster's attempted proof. Euler's theorem broadens the possibilities, but while allowing a non-prime modulus it also restricts the base to numbers relatively prime to the modulus. --KSmrq^T 20:48, 2 August 2007 (UTC)[reply]

Right right... I totally forgot about that caveat. You can, in fact, reduce if and only if those two numbers are co-prime. My mistake -- thanks. Gscshoyru 20:52, 2 August 2007 (UTC)[reply]

Unioted States Businesses Statistics

How many businesses of any and all types are there in the United States? Quarrithbrakka

Um... this is not the place to ask that question... and I'm pretty sure figuring out an answer is near-impossible. You could get someone to give you an estimate, maybe... but an exact answer would be very difficult, if not impossible. Gscshoyru 21:31, 2 August 2007 (UTC)[reply]

Not necessarily, as long as you define your terms a bit more strictly. A little research led me to FedStats, from which I got to the IRS's Tax Stats page, from which you can find information on, among other things, the number of companies that filed a tax return in various years (most of the tables currently stop at or before 2004, but there are ways to estimate the current value from those numbers) - it looks like in 2004, 5,557,965 tax returns were filed by active corporations, and if you were to take a read through their methodology you would doubtless be able to work out whether there's a 1-1 correspondence between companies and tax returns, and if not there might be some hints as to how to fix that. The poster's other question might prove a little trickier, but I'm going to dig a bit to see if I can find some crime statistics somewhere as well (and technically, yes, the reporting of various statistics as opposed to calculations involving them probably belongs on another Reference Desk, but I won't begrudge the poster their decision). Confusing Manifestation 23:20, 2 August 2007 (UTC)[reply]

Keep in mind that not all businesses are corporations. This page lists the different types, when all types of businesses are included there were 26,434,293 businesses in 2002.--Ybbor ^Talk 03:12, 3 August 2007 (UTC)[reply]

most popular stolen car model and year

what is the most commom stolen car model and year

Um... huh? See above. Same answer. Gscshoyru 22:44, 2 August 2007 (UTC)[reply]

Damn, so close. I can tell you that in 2005 822,400 motor vehicle thefts were reported[1] along with a whole lot of statistics on the people whose cars were stolen (thanks to the Bureau of Justice Statistics), but no information on the cars themselves. Their website does have a contact email listed, so you may be able to ask them if they have those numbers themselves. I'm also tracking a couple of other leads, which I'll post here if they lead to anything. Confusing Manifestation 23:28, 2 August 2007 (UTC)[reply]

Two or three years ago it was the Cadillac Escalade.--Cronholm¹⁴⁴ 07:48, 6 August 2007 (UTC)[reply]