# Dominion Strategy Forum

• June 18, 2019, 08:55:01 pm
• Welcome, Guest

### News:

DominionStrategy Wiki

Pages: 1 ... 7 8 [9] 10 11 ... 41  All

0 Members and 1 Guest are viewing this topic.

#### liopoil

• Margrave
• Offline
• Posts: 2587
• Respect: +2476
« Reply #200 on: January 02, 2015, 10:30:31 pm »
0

Oh whoops, made an error with the problem. Um, we'll call that easy mode. But yea, liopoil has it right.
Okay, hard mode:

What is the least prime factor of 252^128 + 1?
So, uhh, the last digit is 7... and so the least prime factor is at the lowest 11...

252 is 10 mod 11. 10^128 + 1 is 127 0s with 1s at either end, so odd number of digits and the 1s are both in 'odd' digits, so the expression is not divisible by 11.

252 is 5 mod 13. Cycle of powers of 5 mod 13 is 5, 12, 8, 1, repeat. 128 is divisible by 4, so the expression is 2 mod 13, not divisible by 13.

252 is 12 mod 17... and I'm starting to get the feeling I need a better approach to solve this.
Logged

#### heron

• Saboteur
• Online
• Posts: 1022
• Respect: +1147
« Reply #201 on: January 02, 2015, 10:58:12 pm »
0

Oh whoops, made an error with the problem. Um, we'll call that easy mode. But yea, liopoil has it right.
Okay, hard mode:

What is the least prime factor of 252^128 + 1?
So, uhh, the last digit is 7... and so the least prime factor is at the lowest 11...

252 is 10 mod 11. 10^128 + 1 is 127 0s with 1s at either end, so odd number of digits and the 1s are both in 'odd' digits, so the expression is not divisible by 11.

252 is 5 mod 13. Cycle of powers of 5 mod 13 is 5, 12, 8, 1, repeat. 128 is divisible by 4, so the expression is 2 mod 13, not divisible by 13.

252 is 12 mod 17... and I'm starting to get the feeling I need a better approach to solve this.

Yea, I wanted to make the answer big enough that you wouldn't want to just check all of the primes in order, but small enough that you can check that the number is actually prime pretty quickly.
Logged

#### liopoil

• Margrave
• Offline
• Posts: 2587
• Respect: +2476
« Reply #202 on: January 02, 2015, 11:49:42 pm »
+1

Call the value of the expression x and its least prime factor n. x is 0 mod n, so 252^128 is n - 1 mod n. Assume n < 128. Since n is prime I think (not sure) that means those cycles must have a length which is a factor of n - 1. Then (252 mod n)^ (128 mod n - 1) is n - 1 mod n. This rules out 17. Plugging in 19 we get 5 squared which is not 18 mod 19. For 23 we get 22 ^ 18, but since 22 is the first term in the cycle and 18 isn't anywhere near a factor of 22 we see it doesn't work without computation. 29 yields 20 ^ 16. Yikes. 31 yields 4 ^ 4 = 256, which is congruent to 10 (mod 31) which is not 30. Okay back to thinking more generally...

Okay maybe n > 128. I think all my statements are still true, just less useful.  I don't know what I'm doing, and am increasingly feeling like I'm entirely on the wrong track. I don't know anything about these cycles!
Logged

#### heron

• Saboteur
• Online
• Posts: 1022
• Respect: +1147
« Reply #203 on: January 02, 2015, 11:58:04 pm »
0

You are more on the right track than you think.

Some things you might want to consider/hints:

I'll call the least prime factor p.
Yes, 252^128 = -1 (mod p). And yes, 252^n is periodic modulo p, where the period is a factor of p-1. Make sure you know why it is a factor of p-1.
In other words, p-1 is a multiple of the period. Now, if only you knew what the period was...
Logged

#### GeoLib

• Jester
• Offline
• Posts: 965
• Respect: +1263
« Reply #204 on: January 03, 2015, 01:47:53 am »
+3

Here's a classic problem:

What is the least prime factor of 63^128 + 1?
Does this work?

63 = 7*3^2, so 63^128 + 1 = 7^128*3^256 + 1

The last digits of powers of 3 are 3, 9, 7, 1, repeat. 256 is divisible by 4 so the power of 3 term ends in 1.

The last digits of powers of 7 end in 7, 9, 3, 1, repeat. 128 is divisible by 4 so the power of 7 term ends in 1. Their product must also end in 1 then. Add one and the expression ends in 2. Therefore the number is divisible by 2, which is the smallest prime that there is. So the answer is 2.

So for the easy version, Can't we just say 3^256*7^128 is odd, so add one and it must be even, so 2?
Logged
—Count Grishnakh

#### Titandrake

• Mountebank
• Offline
• Posts: 2105
• Respect: +2606
« Reply #205 on: January 03, 2015, 03:35:19 am »
+1

Ooh, I do so love a number theory puzzle. I think it's the correct answer but there are gaps in my proof that I'm working on fixing.

We want the smallest prime p such that 252^128 = -1 mod p.

Since we're always going to work mod some prime p, by Fermat's Little Theorem a^{p-1} = 1 mod p. In particular, this gives that for any k such that a^k = 1 mod p, k must be a factor of p-1. I'm sure there's a way to prove this without too much machinery, but I'll just cite Lagrange's Theorem and move on.

We know a^n is periodic in mod p. First, we need to show a^n = -1 for some n mod p.  Here's the hole: not sure how you do this.

Let k be the period, meaning the smallest positive exponent where a^k = 1. Let k' be the power such that a^k' = -1, where k' < k. Then since a^{2k'} = (-1)^2 = 1, we must have k' = k / 2. Quick proof: if k' < k/2, then 2k' < k and k cannot be the period since a^{2k'} = a^0 = 1, a contradiction. If k' > k/2, then a^{2k' - k} = 1 as well, and 2k' - k < k, also a contradiction. Therefore, we must have k' = k / 2.

So, in particular, this gives that the powers such that a^n = -1 mod p are k/2, 3k/2, 5k/2, 7k/2, ... or equivalently some odd multiple of k'. But 128 is a power of 2. Therefore, we must have k' = 128 => k = 256. So, 256 is a factor of p-1. Luckily, it turns out 257 is prime, so the answer is 257.

Edit: Have verified with computer my answer is correct. Working on the hole-filling now.

Edit 2: Some general cleaning up.
« Last Edit: January 03, 2015, 05:36:13 am by Titandrake »
Logged
I have a blog! It's called Sorta Insightful. Check it out?

#### heron

• Saboteur
• Online
• Posts: 1022
• Respect: +1147
« Reply #206 on: January 03, 2015, 11:08:06 am »
0

You have the correct answer there, here is a comment and a method to prove that your answer is indeed a factor:

Yea, it is much more annoying to work with -1 mod p than with 1 mod p. It gets a lot less messy if you multiply by 252^128-1 to get 252^256 - 1. Then you know a^n = 1 mod p where n is a factor of 256, and you can quickly ascertain that n is not a factor of 128, because then p|252^128 - 1.
So 256|p-1, and as you noted, 257 is prime.

Probably the fastest way to check that 257|252^128 + 1 is via Euler's criterion for quadratic residues and quadratic reciprocity. Euler's criterion tells us that a^((p-1)/2) = 1 (mod p) if a is a quadratic residue mod p and -1 if it is a nonresidue. 252 = 7*6^2, and so (6^((257-1)/2))^2 = 1 (mod 257). So we want that 7^128 = -1 (mod 257). From the quadratic reciprocity law, 7^128 (mod 257) and 257^3 (mod 7) are either both +1 or both -1, since 7 and 257 are not both 3 (mod 4). So, 257^3 = 5^3 = -1 (mod 7), so 7^128 = -1 (mod 257). So that's it, 252^128 + 1 = 0 (mod 257).
Logged

#### liopoil

• Margrave
• Offline
• Posts: 2587
• Respect: +2476
« Reply #207 on: January 03, 2015, 11:39:23 am »
0

Here's a classic problem:

What is the least prime factor of 63^128 + 1?
Does this work?

63 = 7*3^2, so 63^128 + 1 = 7^128*3^256 + 1

The last digits of powers of 3 are 3, 9, 7, 1, repeat. 256 is divisible by 4 so the power of 3 term ends in 1.

The last digits of powers of 7 end in 7, 9, 3, 1, repeat. 128 is divisible by 4 so the power of 7 term ends in 1. Their product must also end in 1 then. Add one and the expression ends in 2. Therefore the number is divisible by 2, which is the smallest prime that there is. So the answer is 2.

So for the easy version, Can't we just say 3^256*7^128 is odd, so add one and it must be even, so 2?
Or just Odd number to natural power is odd, so add one and it must be even, so 2. I didn't expect it to be so easy, so I wrote more.

Still working on the real problem, haven't read Titandrake's solution or heron's comment on it.
Logged

#### Kirian

• Offline
• Posts: 7089
• An Unbalanced Equation
• Respect: +9358
« Reply #208 on: January 04, 2015, 09:33:31 am »
+2

Here's a classic problem:

What is the least prime factor of 63^128 + 1?

Moat?

For some reason, this joke never gets old.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### Awaclus

• Offline
• Posts: 11154
• (´｡• ω •｡`)
• Respect: +11814
« Reply #209 on: January 04, 2015, 09:47:31 am »
+4

Logged
Bomb, Cannon, and many of the Gunpowder cards can strongly effect gameplay, particularly in a destructive way

#### liopoil

• Margrave
• Offline
• Posts: 2587
• Respect: +2476
« Reply #210 on: January 04, 2015, 10:38:39 am »
0

I think we need to get more creative. Whenever I see ~5 characters of spoiler-ed text I immediately know what it says. Add some spaces at one end or something! That would make it funnier.
Logged

#### SwitchedFromStarcraft

• Saboteur
• Offline
• Posts: 1088
• Respect: +852
« Reply #211 on: January 04, 2015, 10:53:34 am »
0

I think we need to get more creative. Whenever I see ~5 characters of spoiler-ed text I immediately know what it says. Add some spaces at one end or something! That would make it funnier.

Like I did in the first spoiler here:

Logged
Quote from: Donald X.
Posting begets posting.

Quote from: Asper
Donald X made me a design snob.

There is a sucker born every minute.

#### Awaclus

• Offline
• Posts: 11154
• (´｡• ω •｡`)
• Respect: +11814
« Reply #212 on: January 04, 2015, 11:14:21 am »
+2

I think we need to get more creative. Whenever I see ~5 characters of spoiler-ed text I immediately know what it says. Add some spaces at one end or something! That would make it funnier.

But you still have to check every time.
Logged
Bomb, Cannon, and many of the Gunpowder cards can strongly effect gameplay, particularly in a destructive way

#### sudgy

• Cartographer
• Offline
• Posts: 3362
• It's pronounced "SOO-jee"
• Respect: +2627
« Reply #213 on: January 04, 2015, 11:44:14 am »
+3

I think we need to get more creative. Whenever I see ~5 characters of spoiler-ed text I immediately know what it says. Add some spaces at one end or something! That would make it funnier.

But you still have to check every time.

You see the spoiler, and the first thing you think when you see it, is "Is it Haha!"
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

Quote from: sudgy on June 31, 2011, 11:47:46 pm

#### SwitchedFromStarcraft

• Saboteur
• Offline
• Posts: 1088
• Respect: +852
« Reply #214 on: January 04, 2015, 11:47:36 am »
+5

I always check, on the theory that one day it will read "Is it Ozle?"
Logged
Quote from: Donald X.
Posting begets posting.

Quote from: Asper
Donald X made me a design snob.

There is a sucker born every minute.

#### sudgy

• Cartographer
• Offline
• Posts: 3362
• It's pronounced "SOO-jee"
• Respect: +2627
« Reply #215 on: January 15, 2015, 03:28:02 pm »
0

So, there's something I've been wondering.  As far as I understand, here's how you solve the differential equation y' = y:

y' = y
dy/dx = y
dy/y = dx
∫dy/y = ∫dx
ln |y| = x + C
|y| = e^(x + C)
|y| = (e^x)*(e^C)
Since e^C is any positive number:
|y| = Ce^x (C > 0)
Getting rid of the absolute value allows the right side to be negative:
y = Ce^x (C ≠ 0)

The problem is, C = 0 is a solution, but I don't see how to make it a part of the process of getting the solution.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

Quote from: sudgy on June 31, 2011, 11:47:46 pm

#### Witherweaver

• Offline
• Posts: 6476
• Respect: +7827
« Reply #216 on: January 15, 2015, 03:32:57 pm »
+1

Logged

#### heron

• Saboteur
• Online
• Posts: 1022
• Respect: +1147
« Reply #217 on: January 15, 2015, 03:33:44 pm »
+4

I think the problem is that when you go from dy/dx = y to dy/y = dx, you assume that y ≠ 0.
Logged

#### Witherweaver

• Offline
• Posts: 6476
• Respect: +7827
« Reply #218 on: January 15, 2015, 03:34:39 pm »
0

So, there's something I've been wondering.  As far as I understand, here's how you solve the differential equation y' = y:

y' = y
dy/dx = y
dy/y = dx
∫dy/y = ∫dx
ln |y| = x + C
|y| = e^(x + C)
|y| = (e^x)*(e^C)
Since e^C is any positive number:
|y| = Ce^x (C > 0)
Getting rid of the absolute value allows the right side to be negative:
y = Ce^x (C ≠ 0)

The problem is, C = 0 is a solution, but I don't see how to make it a part of the process of getting the solution.

C=0 => y=0 => y'/y does not make many senses.

Edit: Ninja'd
Logged

#### sudgy

• Cartographer
• Offline
• Posts: 3362
• It's pronounced "SOO-jee"
• Respect: +2627
« Reply #219 on: January 15, 2015, 03:37:50 pm »
0

So, even though d/dx 0 = 0 it doesn't satisfy the equation y' = y?
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

Quote from: sudgy on June 31, 2011, 11:47:46 pm

#### Witherweaver

• Offline
• Posts: 6476
• Respect: +7827
« Reply #220 on: January 15, 2015, 03:42:26 pm »
0

So, even though d/dx 0 = 0 it doesn't satisfy the equation y' = y?

It satisfies the equation, but if you're going to tell me that 1 = kx (for some finite real k) and therefore 1/x = k, you're also implicitly telling me that x is not zero.
Logged

#### scott_pilgrim

• Saboteur
• Offline
• Posts: 1024
• Respect: +1995
« Reply #221 on: January 15, 2015, 03:43:34 pm »
0

So, even though d/dx 0 = 0 it doesn't satisfy the equation y' = y?

Yes it does, it's an alternate solution.  Whenever you divide by a variable (this applies to basic algebra as well), you have to check whether that variable could be 0; in this case, it can.  For example, 0 is a solution of x=x^3, even though you only get 1 or -1 when you divide both sides by x.
Logged

#### Polk5440

• Torturer
• Offline
• Posts: 1708
• Respect: +1782
« Reply #222 on: January 15, 2015, 03:43:55 pm »
0

So, there's something I've been wondering.  As far as I understand, here's how you solve the differential equation y' = y:

y' = y
dy/dx = y
dy/y = dx

You rule out y = 0 as a solution here because you divide by y and then integrate. You can't do this if y is identically equal to zero. So the solution method misses the trivial solution (y = 0 implies y' = 0 so that works as a solution). But normally people don't care about the trivial solutions, so it's not a big deal in this case.

[analytic details about integration go here]

Ninja'd...

Edit: scott says it better...
Logged

#### Witherweaver

• Offline
• Posts: 6476
• Respect: +7827
« Reply #223 on: January 15, 2015, 03:45:06 pm »
0

In other words, your solution technique only finds nonzero y that solves y' = y.

Then you can simply observe that y=0 solves the equation as well, so that

y(x) = Ce^x

describes a family of solutions for all real C.
Logged

#### sudgy

• Cartographer
• Offline
• Posts: 3362
• It's pronounced "SOO-jee"
• Respect: +2627
« Reply #224 on: January 15, 2015, 03:45:53 pm »
0

Ah, I get it now.  Thanks!
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

Quote from: sudgy on June 31, 2011, 11:47:46 pm
Pages: 1 ... 7 8 [9] 10 11 ... 41  All

Page created in 0.193 seconds with 21 queries.