inshm2016 Posted August 26, 2015 Report Share Posted August 26, 2015 Hi, If I have chosen number 24900 and need to find a number X such that 22133*X - 1 = a multiple of 24900, how do I do it? Is there a certain method? I have tried trial and error but to no avail :/ Grateful for replies Reply Link to post Share on other sites More sharing options...
Vioh Posted August 26, 2015 Report Share Posted August 26, 2015 Hi, If I have chosen number 24900 and need to find a number X such that 22133*X - 1 = a multiple of 24900, how do I do it? Is there a certain method? I have tried trial and error but to no avail :/ Grateful for replies This problem can be re-formulated like this:Find 2 integers x and y, such that they satisfy: If you have done the Discrete Maths HL option, then you would realize that it's possible to apply the Euclidean Algorithm backwards in order to solve this problem. So let's begin! First, we apply the Euclidean Algorithm using the 2 integers 22133 and 24900 as follows:Line 1: Line 2: Line 3: Line 4: For line 1, we call 24900 the dividend, 22133 the divisor, 1 the quotient, and 2767 the remainder; Then the Euclidean Algorithm simply tells us to make the divisor of line 1 to become the dividend of line 2, and to make the remainder of line 1 to become the divisor of line 2. Then we'll have to find the quotient and the remainder for line 2. The same process is repeated for line 3 & 4. Euclidean algorithm can only be stopped if you get 1 as the remainder (which is exactly what it is for line 4). I'll leave you there you understand why that must be the case. Now, let's apply the Euclidean Algorithm backwards. From line 4, we have:Our job now is to re write this equation above using only 24900, 22133, and 2 other integers (eventually for x & y) based on the information in line 1, 2, and 3. This might look complicated, but just follow the common sense: (from line 4) (from line 2 & 3) (from line 1 & 2) (from line 1) Clearly, from the result above, we know that and Check that using your calculator, and you'll see the magic result. Feel free to ask if you have further questions! Reply Link to post Share on other sites More sharing options...
inshm2016 Posted August 26, 2015 Author Report Share Posted August 26, 2015 Hi, If I have chosen number 24900 and need to find a number X such that 22133*X - 1 = a multiple of 24900, how do I do it? Is there a certain method? I have tried trial and error but to no avail :/ Grateful for replies This problem can be re-formulated like this:Find 2 integers x and y, such that they satisfy: If you have done the Discrete Maths HL option, then you would realize that it's possible to apply the Euclidean Algorithm backwards in order to solve this problem. So let's begin! First, we apply the Euclidean Algorithm using the 2 integers 22133 and 24900 as follows:Line 1: Line 2: Line 3: Line 4: For line 1, we call 24900 the dividend, 22133 the divisor, 1 the quotient, and 2767 the remainder; Then the Euclidean Algorithm simply tells us to make the divisor of line 1 to become the dividend of line 2, and to make the remainder of line 1 to become the divisor of line 2. Then we'll have to find the quotient and the remainder for line 2. The same process is repeated for line 3 & 4. Euclidean algorithm can only be stopped if you get 1 as the remainder (which is exactly what it is for line 4). I'll leave you there you understand why that must be the case. Now, let's apply the Euclidean Algorithm backwards. From line 4, we have:Our job now is to re write this equation above using only 24900, 22133, and 2 other integers (eventually for x & y) based on the information in line 1, 2, and 3. This might look complicated, but just follow the common sense: (from line 4) (from line 2 & 3) (from line 1 & 2) (from line 1) Clearly, from the result above, we know that and Check that using your calculator, and you'll see the magic result. Feel free to ask if you have further questions! OMG THANK YOU!! Reply Link to post Share on other sites More sharing options...
Master_Domain560 Posted August 27, 2015 Report Share Posted August 27, 2015 Hi, If I have chosen number 24900 and need to find a number X such that 22133*X - 1 = a multiple of 24900, how do I do it? Is there a certain method? I have tried trial and error but to no avail :/ Grateful for replies This problem can be re-formulated like this:Find 2 integers x and y, such that they satisfy: If you have done the Discrete Maths HL option, then you would realize that it's possible to apply the Euclidean Algorithm backwards in order to solve this problem. So let's begin! First, we apply the Euclidean Algorithm using the 2 integers 22133 and 24900 as follows:Line 1: Line 2: Line 3: Line 4: For line 1, we call 24900 the dividend, 22133 the divisor, 1 the quotient, and 2767 the remainder; Then the Euclidean Algorithm simply tells us to make the divisor of line 1 to become the dividend of line 2, and to make the remainder of line 1 to become the divisor of line 2. Then we'll have to find the quotient and the remainder for line 2. The same process is repeated for line 3 & 4. Euclidean algorithm can only be stopped if you get 1 as the remainder (which is exactly what it is for line 4). I'll leave you there you understand why that must be the case. Now, let's apply the Euclidean Algorithm backwards. From line 4, we have:Our job now is to re write this equation above using only 24900, 22133, and 2 other integers (eventually for x & y) based on the information in line 1, 2, and 3. This might look complicated, but just follow the common sense: (from line 4) (from line 2 & 3) (from line 1 & 2) (from line 1) Clearly, from the result above, we know that and Check that using your calculator, and you'll see the magic result. Feel free to ask if you have further questions! Jesus christ man. The time you have as a post IB university student! Reply Link to post Share on other sites More sharing options...
inshm2016 Posted August 27, 2015 Author Report Share Posted August 27, 2015 Feel free to ask if you have further questions! Really, a big thanks for the help. Assisted me very much in my project.I have one last question before finishing my work: Why is the mutiplicative order always a divisor of p-1? I thought that it only had to be less or equal to p-1. This question pertains to finding primitive roots Reply Link to post Share on other sites More sharing options...
Vioh Posted August 29, 2015 Report Share Posted August 29, 2015 Jesus christ man. The time you have as a post IB university student! Lol, posting on IBS takes way less time compared to all those philosophical debates that I have with you haha. Really, a big thanks for the help. Assisted me very much in my project.I have one last question before finishing my work: Why is the mutiplicative order always a divisor of p-1? I thought that it only had to be less or equal to p-1. This question pertains to finding primitive roots Uhm... I think this question should belong to this thread of yours instead. Anyway, the answer is quite simple if you use Fermat's Little Theorem together with some intuitions when working with modulo. So we know that if is to be the primitive root of , then must be the smallest positive integer that satisfies . This means that in which . And in addition to that, since is the smallest positive integer, we know from our intuition that all powers of that are congruent to must be of the form . Now, Fermat's Little Theorem states that for a prime number , it is true that . This, together with the result of the above paragraph, tells us that must be of the form , which simply implies that is a factor of . And that's it!!!Tell me if you have any problems understanding my explanation. Reply Link to post Share on other sites More sharing options...
inshm2016 Posted August 29, 2015 Author Report Share Posted August 29, 2015 Jesus christ man. The time you have as a post IB university student! Lol, posting on IBS takes way less time compared to all those philosophical debates that I have with you haha. Really, a big thanks for the help. Assisted me very much in my project.I have one last question before finishing my work: Why is the mutiplicative order always a divisor of p-1? I thought that it only had to be less or equal to p-1. This question pertains to finding primitive roots Uhm... I think this question should belong to this thread of yours instead. Anyway, the answer is quite simple if you use Fermat's Little Theorem together with some intuitions when working with modulo. So we know that if is to be the primitive root of , then must be the smallest positive integer that satisfies . This means that in which . And in addition to that, since is the smallest positive integer, we know from our intuition that all powers of that are congruent to must be of the form . Now, Fermat's Little Theorem states that for a prime number , it is true that . This, together with the result of the above paragraph, tells us that must be of the form , which simply implies that is a factor of . And that's it!!!Tell me if you have any problems understanding my explanation. THANK YOU SO MUCH. I really appreciate the time you spent helping me. Finally done with the IA :D Reply Link to post Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.