Author |
Topic: Add To Power And Divide, Get Integer? (Read 263 times) |
|
K Sengupta
Senior Riddler
Gender: 
Posts: 371
|
 |
Add To Power And Divide, Get Integer?
« on: Aug 6th, 2007, 8:20am » |
 Quote  Modify
|
Analytically determine whether for every positive integer P, there always exists a positive integer Q such that 3Q+5 is divisible by 2P
|
|
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Add To Power And Divide, Get Integer?
« Reply #1 on: Aug 6th, 2007, 8:51am » |
Quote Modify
|
yes:
| hidden: | We prove by induction that for P  3, there is a Q such that 3Q+5 is divisible by 2P, and no larger power.
Suppose that 3Q + 5 = t*2P, where t is is odd. Then we need to find Q' = Q+R such that
3Q' + 5 = 3R(t*2P - 5) + 5  2P + (3R - 1) 0 mod 2P+1.
This will happen when 3R-1 is divisible by 2P, but no larger power. But the order of 3 mod 23 is 2, and this implies that, for P 3, the order of 3 mod 2P is 2P-2. We therefore take Q' = Q + 2P-2. |
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Add To Power And Divide, Get Integer?
« Reply #2 on: Aug 6th, 2007, 9:02am » |
Quote Modify
|
Another solution:
| hidden: | Z2^P* = Z2^(P-2) x Z2, where the first factor is generated by 5 = (1,0), and the second factor is generated by -1 = (0,1).
Let P 3, and let 3 = (a,b). Now, 3 is not a power of 5 mod 4, so b=1. And a can't be even, otherwise we'd have 3 = -5a = 7 mod 8. So 3 = (a,1), where a is odd. So there is some Q such that Q*a = 1 mod 2P-2, so 3Q = (1,1) = -5. |
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print