Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[wierd]

I would say  (as a haphazard guess without looking terribly closely)  that the resulting residues for coprime and prime numbers has to do with the universality of primeness.  Changing the modulo operator is essentially just like changing the number system base.

Prime numbers are prime in every number system base.


Just an idea though, dont want to try proving it.  Just that logically, a modulo operation is just working on the number system unit.

EG, the normal unit in our decimal system is 10, so doing a MOD 10, is basically just moving the decimal place over, and returning trailing figure.

EG, 11 MOD 10 = 1

is functionally moving the decimal place to the left, discarding the whole fraction, and returning the decimal portion.

11 -> 1.1
(discard whole fraction) -> .1 (Treat as whole number) -> 1

Modulo of any arbitrary number is the functional equivalent of such decimal shift and return of residue, except the results are presented as a base 10 number.

10 MOD 7, for instance, is taking the base 7 number 13 (10 decimal is 13 in base 7), moving the decimal point left one place, discarding the whole portion, and returning the residue. (3)

Or say, 15 MOD 5 = 0

(15 in base 5 is 30)
30 -> 3.0 ->(discard whole portion and return residue, treat as whole number) -> 0

Since primeness is exhibited in all number systems, its unique properties will manifest in such operations.

[Maximum Spin]

It will always become periodic eventually.

Consider multiplication of x × (ab+c) where b is the base. Result: abx+cx. Simple enough. Now consider: abx is already a multiple of the base and will end in 0 in our normal place-based numbering system, so the last digit depends entirely on c, which happens to also be (ab+c) mod b (and thus the last digit of that multiplicand in base b). As such, it becomes obvious that (abx + cx) mod b = cx mod b depends entirely on (ab + c) mod b = c mod b, right? This means that every entry in your table depends entirely on the entry above it, and is (cx) mod b where c is that entry. GIVEN that it depends entirely on another value mod b, and that there are only b possible values mod b (0 .. b-1), there are a finite number of possible 'states' for the table to be in, which is to say, the set of states 'c mod b = (0 .. b-1)'. This means that the table is a finite state machine, and a finite state machine always either terminates or loops. Numbers don't terminate, so it will always loop. That is to say, because there are a finite number of possible states, and they are 'selected from' infinitely, a state which has previously been selected must eventually be selected again (obviously), and, because the next outcome depends entirely on the previous state, that means it will proceed through exactly the same path between those points again, forever. In case you didn't notice, this is general to all starting points, not just starting with (a₀b+c₀) = x, but applies there as well.

The reason that the result has periodicity 1 in many cases when (a₀b+c₀) does = x is also straightforward: it applies when some power of x z has the relation x × (z mod b) mod b = z mod b. This happens, for example, with 0, 5, and 6 right out the gate at z = x under base 10: 0 × 0 = 0, 5 × 5 = 25 (and 25 mod 10 = 5), 6 × 6 = 36 (and 36 mod 10 = 6). In these cases, the 'c' in the previous paragraph will be 'z mod b' forever from that point on, because cx mod b, the formula mentioned for the next c, continues to = z mod b. Now, if x and b share all prime factors, then they can both be written ∏n_i^m_i where n_i proceeds through the factors and m_i through their exponents in the particular case. This means that only the ms differ between the two forms, as I hope is obvious. As a result, x^j can be written ∏n_i^m_ij, yes? Basic principle of exponents there: for all n, e, t, n^et = n^et. That means that, eventually, for some sufficiently large j, x^j's 'm_ij's will all be bigger than b's 'm_i's, at which point x^j is a multiple of b, so x^j mod b = 0. This is what is inhering in your 6^x mod 12 case: 6 is 2¹×3¹ and 12 is 2²×3¹. 6² = 36 is 2²×3², logically, which is then a multiple of 12, in fact: 12 × 3. Therefore 36 mod 12 is 0, obviously enough, and gets stuck there because 0x mod 12 will always be 0 (because 0x is always 0).

I feel like I've written too much now to move on to the 5 mod 10 and 6 mod 10 cases, but suffice to say that the number of cs you iterate through depends on the arithmetical relationship between x and b.

ETA: All right, I can't not explain it. When x² - x mod b = 0, x² mod b will = x mod b. This is easily demonstrable because x² mod b is x² - x mod b + x mod b, right? So 0 + x mod b = x mod b. This happens when x and x-1 together cover all the factors of b, so that x × (x-1) ( = x² - x) is a multiple of b. This covers the 5 and 6 mod 10 cases, where 5 × 4 = 20 (because 5 = 5¹ and 4 = 2², and 10 is 5¹×2¹. 5¹ × 2² is then a multiple of 10, right? The same thing happens with 6 × 5 because 6 has the '2' factor and 5, obviously, covers itself.

[WealthyRadish]

What you're doing here is using the number n as a generator. When the generating number and the modulo base are coprime you get a cyclic group (all of the column sequences containing 1 are groups), but the others are just finite sets with closure and have fewer interesting properties.

Notice that if you multiply any of the numbers together in the column and then again apply the modulo, you'll get another number in the column (i.e. the modulo operation doesn't change that a * a^y = a^y+1).

Another thing you can notice in that mod 10 table is that the groups generated by 3 and 7 (prime numbers that aren't divisors of 10) are the same (and largest) group, and contain all the numbers between 1 and 9 relatively prime to 10 (this particular group is sometimes labelled "U(10)"), and that the group generated by 9 (3²) is a cyclic subgroup of this.

Courses in university with names like "Abstract Algebra" or "Galois Theory" or something with "group" in the name deal with stuff like this.

[methylatedspirit]

Since each entry in the table depends entirely on the last, does there exist a recurrence relation for it, either for going horizontally or vertically down that table? I'd like to generate that same table, but with a modulus of something like 997 instead of just 10 without busting out an arbitrary precision calculator. The naive method (which I've been doing) is to just calculate f_horizontal(n) = n^a mod b or f_vertical(n) = aⁿ mod b.

Either one ends up ballooning to huge numbers in the process of calculating it once I get up to such high values of b, far outside of the 15 significant figures given by single-precision floating-point, which is the only format that the tools I've been using support. Just doing double-, quadruple-, or octuple-precision wouldn't work, since I'd eventually have to calculate 997⁹⁹⁷ (for that 'b = 997' table), which has 2990 decimal digits. That would need some ridiculous precision to store without shaving off the last digits. I'm not particularly keen on programming in something that supports arbitrarily-large integers, either, since I'm not a coder myself.

[A_Curious_Cat]

Just out of curiosity...

How (assuming one wanted to) would one convert a horse drawn threshing machine into a 2 door sport coupe with a v6?

[Maximum Spin]

Since each entry in the table depends entirely on the last, does there exist a recurrence relation for it, either for going horizontally or vertically down that table? I'd like to generate that same table, but with a modulus of something like 997 instead of just 10 without busting out an arbitrary precision calculator. The naive method (which I've been doing) is to just calculate f_horizontal(n) = n^a mod b or f_vertical(n) = aⁿ mod b.

Yes, if 'c' is the previous entry, the next entry vertically is 'xc mod b', so you never have to calculate anything higher than 997×996.

Just out of curiosity...

How (assuming one wanted to) would one convert a horse drawn threshing machine into a 2 door sport coupe with a v6?

It seems pretty straightforward (just saw off the bits that aren't a 2-door sport coupe with a v6, then install the additional parts you need to make it into one), but you'd have a wooden coupe. Of course you could also just replace the wood with metal, but that's pretty Ship of Theseus.

[methylatedspirit]

Since each entry in the table depends entirely on the last, does there exist a recurrence relation for it, either for going horizontally or vertically down that table? I'd like to generate that same table, but with a modulus of something like 997 instead of just 10 without busting out an arbitrary precision calculator. The naive method (which I've been doing) is to just calculate f_horizontal(n) = n^a mod b or f_vertical(n) = aⁿ mod b.

Yes, if 'c' is the previous entry, the next entry vertically is 'xc mod b', so you never have to calculate anything higher than 997×996.

I'm feeling a bit dumb here. So if f(x) = c, then f(x+1) = xc mod b? Just for a bit of sanity-checking, if I started with b = 10, and c = 2, then it goes:
f(x) = 2^x mod 10
f(x + 1) = 2*f(x) mod 10, where f(1) = 2.
So:
f(1) = 2 mod 10 = 2,
f(2) = 2f(1) mod 10 = 4 mod 10 = 4
But then
f(3) = 3f(2) mod 10 = 3*4 mod 10 = 12 mod 10 = 2,
which is incorrect, as f(3) should be 2³ mod 10 = 8. Something must have gone wrong, but I'm not sure if it's me misunderstanding you (which is likely) or if what you're giving me is incorrect (less likely, but a perfectly probable possibility).

[Maximum Spin]

Since each entry in the table depends entirely on the last, does there exist a recurrence relation for it, either for going horizontally or vertically down that table? I'd like to generate that same table, but with a modulus of something like 997 instead of just 10 without busting out an arbitrary precision calculator. The naive method (which I've been doing) is to just calculate f_horizontal(n) = n^a mod b or f_vertical(n) = aⁿ mod b.

Yes, if 'c' is the previous entry, the next entry vertically is 'xc mod b', so you never have to calculate anything higher than 997×996.

I'm feeling a bit dumb here. So if f(x) = c, then f(x+1) = xc mod b? Just for a bit of sanity-checking, if I started with b = 10, and c = 2, then it goes:
f(x) = 2^x mod 10
f(x + 1) = 2*f(x) mod 10, where f(1) = 2.
So:
f(1) = 2 mod 10 = 2,
f(2) = 2f(1) mod 10 = 4 mod 10 = 4
But then
f(3) = 3f(2) mod 10 = 3*4 mod 10 = 12 mod 10 = 2,
which is incorrect, as f(3) should be 2³ mod 10 = 8. Something must have gone wrong, but I'm not sure if it's me misunderstanding you (which is likely) or if what you're giving me is incorrect (less likely, but a perfectly probable possibility).

No, x is the base of the exponentiation here, following the system I used in my previous post, so, in your example, 2. I would've used 'n' for the argument/exponent since that's what you used in your example.
2 × 4 mod 10 is, of course, 8. 2 × 8 mod 10 is 6, 2 × 6 mod 10 is 2, repeat.

[methylatedspirit]

After reading that and debugging my Excel formulas, I finally got it to work. Thank you. You've helped me do something that I've wanted to do for a really long time: making a 'b = 254' table (could've gone for something bigger, just needed to test the waters) and using Conditional Formatting to color the values in (yeah, I know, dumb dream):

Going downwards, it seems to loop every 127 units, if the red-to-white-to-green strip indicates a loop. It appears to loop at twice the rate, but that's actually a weird thing where it starts off red, goes towards white, but has splotches of green sprinkled in. If you look very closely (or just zoomed in massively on the picture) you can still see the row numbers. This is not at all the intended use for Excel, but I'm fairly sure anything that I do that happens to be art (which I suppose this one qualifies as) arises from not using things as intended.

(Should've gone for a prime number less than, but close to 256, for b, but I couldn't be assed to, and it's getting late here, so I guess I'm posting that one in the Random Things you drew thread.)

[A_Curious_Cat]

<snip>

Damn, I hate these things where you have to cross your eyes.  I can never get them to work.

[Maximum Spin]

Going downwards, it seems to loop every 127 units, if the red-to-white-to-green strip indicates a loop.

(As you'd expect, given that that's half the base)

It appears to loop at twice the rate, but that's actually a weird thing where it starts off red, goes towards white, but has splotches of green sprinkled in.

You can see salients like that, but smaller, at additional "harmonics" where many possible values of x all reach their looping point.

[methylatedspirit]

When I was upgrading my laptop's RAM, I noticed that the old stick of RAM had a darker PCB than the new one. It was a darker shade of green than the new one. Now, I have 2 questions:

1) Do PCBs darken under continuous exposure to elevated temperatures? I've run some distributed computing stuff basically 24/7 for at least 6 months now on this laptop, so that one RAM stick has been continuously exposed to something like 50 - 60°C for months now (no temp sensors on either RAM stick, so I'm guessing from the temps of the NVMe drive in here). There's a metal heat-shield covering the RAM, but I doubt it's effective when you're running stuff 24/7. There's that whole 'correlation does not equal causation' thing, but plastics tend to discolor under high temperatures, so to me it sounds plausible.

2) Is this a bad thing? Will the discoloration of the PCB (or the continuous exposure to high temperatures, come to think of it) make my RAM stop working after a while?

[Maximum Spin]

Truthfully, PCBs come in different shades. I even have some in blue for some reason. Unless they are meant to be identical, from identical manufacturers, I wouldn't worry.

[TD1]

Okay folks, what's that abbreviation we all use at the end of a lengthy text paragraph to sum it up?

So, like: Dogs are inherently superior to cats because their sense of loyalty is equatable to the sum of their affection.

[The abbreviation]: Dogs are superior because they are more loyal than cats.

[bloop_bleep]

TLDR (too long; didn't read)