Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
General discussion :
Puzzle Of The Week
Author 
Message 

Can you start a Puzzle or Problem Of The Week. Something from the range of High School to 1st year Grad level?
I'll start.
You are walking on a beach and you encounter a Genie. He says: If you can answer this question I will let you pass. Q: 1091 and 1647 are multiplicative inverses of each other in what base or modulo?
 


211
____________
DeleteNull  


211
211 is incorrect
Maybe we should make it Problem Of The Month.  


211
211 is incorrect
Maybe we should make it Problem Of The Month.
Hint: the base or modulo must be greater than the larger of the two multiplicative inverses.  

JimBHonorary cruncher Send message
Joined: 4 Aug 11 Posts: 918 ID: 107307 Credit: 977,945,376 RAC: 45

Q: 1091 and 1647 are multiplicative inverses of each other in what base or modulo?
It seems to me that modulo 2 they're both equal to 1 and 1 is the multiplicative inverse of itself.  


1091*1647 = 1 (mod 1796876) (I don't have the equivalence character handy)
Perhaps not the lowest modulo, but that wasn't the question :).
Edit: Okay, I "cheated" a little after finding the answer above and wrote a python program to brute force it and came up with 2129 as the lowest of 6 correct moduli. Referring to DeleteNull's answer of 211: (#4)449219=211*2129.
____________
Eating more cheese on Thursdays.  


211
211 is incorrect
Maybe we should make it Problem Of The Month.
1091 = 36 (mod 211)
1647 = 170 (mod 211)
36 * 170 = 1 (mod 211)
2129 does it too.
____________
DeleteNull  


211
211 is incorrect
Maybe we should make it Problem Of The Month.
1091 = 36 (mod 211)
1647 = 170 (mod 211)
36 * 170 = 1 (mod 211)
2129 does it too.
2129 is the only correct answer.
 


In Z (the integers) we have:
1091*1647 = 1796877
So if n is the unknown modulus we seek, then:
1796877 == 1 (mod n)
This means that n can be any divisor of 17968771. We factorize:
1796876 = 2^2 * 211 * 2129
So we have the solutions:
n = 1, 2, 4, 211, 422, 844, 2129, 4258, 8516, 449219, 898438, 1796876.
If we require n to exceed 1647, then the solutions are 2129, 4258, 8516, 449219, 898438, 1796876. And if we required that and further that n is a prime, the only solution is 2129. However, as stated in the original post, all twelve n above are solutions.
/JeppeSN  


In Z (the integers) we have:
1091*1647 = 1796877
So if n is the unknown modulus we seek, then:
1796877 == 1 (mod n)
This means that n can be any divisor of 17968771. We factorize:
1796876 = 2^2 * 211 * 2129
So we have the solutions:
n = 1, 2, 4, 211, 422, 844, 2129, 4258, 8516, 449219, 898438, 1796876.
If we require n to exceed 1647, then the solutions are 2129, 4258, 8516, 449219, 898438, 1796876. And if we required that and further that n is a prime, the only solution is 2129. However, as stated in the original post, all twelve n above are solutions.
/JeppeSN
I was wondering how to find the lower mods analytically, thank you. It's been 10+ years since my number theory class in college so I only had the basic workings in my head. Though I would argue, since we are talking about integers here, that n=1 should be excluded, as there is no 1 (mod 1).
____________
Eating more cheese on Thursdays.  


In Z (the integers) we have:
1091*1647 = 1796877
So if n is the unknown modulus we seek, then:
1796877 == 1 (mod n)
This means that n can be any divisor of 17968771. We factorize:
1796876 = 2^2 * 211 * 2129
So we have the solutions:
n = 1, 2, 4, 211, 422, 844, 2129, 4258, 8516, 449219, 898438, 1796876.
If we require n to exceed 1647, then the solutions are 2129, 4258, 8516, 449219, 898438, 1796876. And if we required that and further that n is a prime, the only solution is 2129. However, as stated in the original post, all twelve n above are solutions.
/JeppeSN
My apology, I should have stated or implied that the answer must be Prime.  


211 is prime.
____________
DeleteNull  


211 is prime.
Yes. Of course it follows from my post above that the prime solutions are the prime factors of 2^2 * 211 * 2129, i.e. the primes 2, 211, and 2129. By the way, JimB gave the solution n=2 early (though not as early as you gave n=211). /JeppeSN  


(...) Though I would argue, since we are talking about integers here, that n=1 should be excluded, as there is no 1 (mod 1).
The case n=1 gives the special ring {0} with one element which has some funny properties. In particular its only element 0 is a 1 because it works like a 1 on every element: 0*0=0. /JeppeSN  


Ah, the degenerate (of a sort) case, and most certainly the most trivial of all solutions. I went, perhaps, a little too literal in my thinking, then, that "1" (and thus modulo >1) had to at least be the result. I used to teach math and loved throwing degenerate figures at my geometry students just to see how they'd react and apply the theorems (that usually still worked, though we updated a few in the advanced class to make up for it).
____________
Eating more cheese on Thursdays.  


211 is prime.
Argh... prime and greater than the largest of the multiplicative inverse pair. Think Cryptography.
 

compositeVolunteer tester Send message
Joined: 16 Feb 10 Posts: 1022 ID: 55391 Credit: 887,943,190 RAC: 142,031

1091*1647 = 1 (mod 1796876) (I don't have the equivalence character handy)
Perhaps not the lowest modulo, but that wasn't the question :).
Edit: Okay, I "cheated" a little after finding the answer above and wrote a python program to brute force it and came up with 2129 as the lowest of 6 correct moduli. Referring to DeleteNull's answer of 211: (#4)449219=211*2129.
I saw an interesting coincidence while verifying that 4 x 449219 = 1796876.
I meant to check 4 x 449219 = 1796876
But I typed 4 x 44219 = 176876
What immediately leaps out is that the third digit from the left (9) in the decimal notation for the number is squeezed out in both the LHS and RHS of the bottom version. I was curious to see why.
TLDR; It happens when the omitted digit is a 9 and the multipliers on the LHS produce a 9 in the product.
I leave it as a challenge to the interested reader to see if other digits can produce this effect.
Taking the difference of the two equations, we have
4 x (449219  44219) = 1796876  176876
whose value D is the 5smooth number 1620000 with prime factorization: 2 2 2 2 2 3 3 3 3 5 5 5 5
We partition the factors of D for both the LHS and RHS of the difference of equations to understand what is happening.
Calling the squeezed digit M, in the Rth place (counting from 1) from the right end of D, M contributes M x 10 ^ (R  1) to the total value of D.
This contribution is a multiple of (R  1) 2s and 5s.
In the LHS the squeezed digit 9 is at R = 4, and in the RHS it is at R = 5.
For the RHS the squeezed digit's position accounts for the factors 2 2 2 2 5 5 5 5 of D.
The remaining factors are 2 3 3 3 3, which multiply to 162 = 179  17.
This expression generalizes as Q x 10 + M  Q = Q x 9 + M.
Since M is 9 we can rewrite this as 9 x (Q + 1).
Two of those remaining 3s are from the squeezedout digit 9 and the remaining factors 2 3 3 are those of 17 + 1.
So that's the partitioning of the factors of the RHS.
On the LHS side R is 4, leaving the prime factors of 1620 = 4 x (449  44) as unrelated to the position of the digit M.
These factors are 2 2 3 3 3 3 5.
The multiplier 4 accounts for the two 2s, leaving 3 3 3 3 5 as the factors of 405 = 449  44 = 9 x (44 + 1).  

Message boards :
General discussion :
Puzzle Of The Week 