GCD and exponentiation of large numbers

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
-2
down vote

favorite












I am solving a problem involving $gcd$ of two very large numbers. Given three numbers $a,b,n$, I have to find $gcd(a,b^n)$. So for example
$$a,b,n=119929244861828206, 521483382396998375, 4838134431180356$$
I used fast modular exponentiation to find
$$521483382396998375^4838134431180356bmod 1000000007=473264774$$
Then I used python's math.gcd module to calculate $gcd(119929244861828206,473264774)$ and got the answer as 2 but the answer is given as 83. I am not sure what mistake I did, so please guide me.




exponentiation greatest-common-divisor




share|cite|improve this question


















  • 1




    Why did you reduce it mod $100000000007$?
    – ThomasGrubb
    Aug 16 at 4:53










  • @ThomasGrubb Presumably because of codechef.com/AUG18B/problems/GCDMOD
    – Lord Shark the Unknown
    Aug 16 at 4:56










  • $n $ is large enough to be irrelevent. If $a $ and $b $ have any prime factor $p $ in common and $p^k $ divides $a $ then $k <n $ and $p^k|b^n $ and the highest power in the gcd has to be whatever the highest power dividing $a $ is.
    – fleablood
    Aug 16 at 6:00














up vote
-2
down vote

favorite












I am solving a problem involving $gcd$ of two very large numbers. Given three numbers $a,b,n$, I have to find $gcd(a,b^n)$. So for example
$$a,b,n=119929244861828206, 521483382396998375, 4838134431180356$$
I used fast modular exponentiation to find
$$521483382396998375^4838134431180356bmod 1000000007=473264774$$
Then I used python's math.gcd module to calculate $gcd(119929244861828206,473264774)$ and got the answer as 2 but the answer is given as 83. I am not sure what mistake I did, so please guide me.




exponentiation greatest-common-divisor




share|cite|improve this question


















  • 1




    Why did you reduce it mod $100000000007$?
    – ThomasGrubb
    Aug 16 at 4:53










  • @ThomasGrubb Presumably because of codechef.com/AUG18B/problems/GCDMOD
    – Lord Shark the Unknown
    Aug 16 at 4:56










  • $n $ is large enough to be irrelevent. If $a $ and $b $ have any prime factor $p $ in common and $p^k $ divides $a $ then $k <n $ and $p^k|b^n $ and the highest power in the gcd has to be whatever the highest power dividing $a $ is.
    – fleablood
    Aug 16 at 6:00












up vote
-2
down vote

favorite









up vote
-2
down vote

favorite











I am solving a problem involving $gcd$ of two very large numbers. Given three numbers $a,b,n$, I have to find $gcd(a,b^n)$. So for example
$$a,b,n=119929244861828206, 521483382396998375, 4838134431180356$$
I used fast modular exponentiation to find
$$521483382396998375^4838134431180356bmod 1000000007=473264774$$
Then I used python's math.gcd module to calculate $gcd(119929244861828206,473264774)$ and got the answer as 2 but the answer is given as 83. I am not sure what mistake I did, so please guide me.




exponentiation greatest-common-divisor




share|cite|improve this question














I am solving a problem involving $gcd$ of two very large numbers. Given three numbers $a,b,n$, I have to find $gcd(a,b^n)$. So for example
$$a,b,n=119929244861828206, 521483382396998375, 4838134431180356$$
I used fast modular exponentiation to find
$$521483382396998375^4838134431180356bmod 1000000007=473264774$$
Then I used python's math.gcd module to calculate $gcd(119929244861828206,473264774)$ and got the answer as 2 but the answer is given as 83. I am not sure what mistake I did, so please guide me.





exponentiation greatest-common-divisor





share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Aug 16 at 4:48









Parcly Taxel

33.6k136588




33.6k136588










asked Aug 16 at 4:46









Vishal .R

11




11







  • 1




    Why did you reduce it mod $100000000007$?
    – ThomasGrubb
    Aug 16 at 4:53










  • @ThomasGrubb Presumably because of codechef.com/AUG18B/problems/GCDMOD
    – Lord Shark the Unknown
    Aug 16 at 4:56










  • $n $ is large enough to be irrelevent. If $a $ and $b $ have any prime factor $p $ in common and $p^k $ divides $a $ then $k <n $ and $p^k|b^n $ and the highest power in the gcd has to be whatever the highest power dividing $a $ is.
    – fleablood
    Aug 16 at 6:00












  • 1




    Why did you reduce it mod $100000000007$?
    – ThomasGrubb
    Aug 16 at 4:53










  • @ThomasGrubb Presumably because of codechef.com/AUG18B/problems/GCDMOD
    – Lord Shark the Unknown
    Aug 16 at 4:56










  • $n $ is large enough to be irrelevent. If $a $ and $b $ have any prime factor $p $ in common and $p^k $ divides $a $ then $k <n $ and $p^k|b^n $ and the highest power in the gcd has to be whatever the highest power dividing $a $ is.
    – fleablood
    Aug 16 at 6:00







1




1




Why did you reduce it mod $100000000007$?
– ThomasGrubb
Aug 16 at 4:53




Why did you reduce it mod $100000000007$?
– ThomasGrubb
Aug 16 at 4:53












@ThomasGrubb Presumably because of codechef.com/AUG18B/problems/GCDMOD
– Lord Shark the Unknown
Aug 16 at 4:56




@ThomasGrubb Presumably because of codechef.com/AUG18B/problems/GCDMOD
– Lord Shark the Unknown
Aug 16 at 4:56












$n $ is large enough to be irrelevent. If $a $ and $b $ have any prime factor $p $ in common and $p^k $ divides $a $ then $k <n $ and $p^k|b^n $ and the highest power in the gcd has to be whatever the highest power dividing $a $ is.
– fleablood
Aug 16 at 6:00




$n $ is large enough to be irrelevent. If $a $ and $b $ have any prime factor $p $ in common and $p^k $ divides $a $ then $k <n $ and $p^k|b^n $ and the highest power in the gcd has to be whatever the highest power dividing $a $ is.
– fleablood
Aug 16 at 6:00










1 Answer
1






active

oldest

votes

















up vote
0
down vote



accepted










If you use the Euclidean algorithm, the first step can be chosen to be computing $b^n$ mod $a$, then compute $a$ mod that, etc. until you get 0. Then back up a step to get the actual GCD, then finally mod by 1000000007 at the end.



Modding by the final modulus at the start changes the result compared to doing it at the end. For instance consider that gcd(11,4) mod 3 is 1 but gcd(11 mod 3,4) is 2.






share|cite|improve this answer






















  • Thank you. Could you also point out the possible cause my solution is not producing the intended result?
    – Vishal .R
    Aug 16 at 5:11










  • @Vishal.R Done.
    – Ian
    Aug 16 at 5:12










Your Answer




StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);








 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2884408%2fgcd-and-exponentiation-of-large-numbers%23new-answer', 'question_page');

);

Post as a guest

















1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
0
down vote



accepted










If you use the Euclidean algorithm, the first step can be chosen to be computing $b^n$ mod $a$, then compute $a$ mod that, etc. until you get 0. Then back up a step to get the actual GCD, then finally mod by 1000000007 at the end.



Modding by the final modulus at the start changes the result compared to doing it at the end. For instance consider that gcd(11,4) mod 3 is 1 but gcd(11 mod 3,4) is 2.






share|cite|improve this answer






















  • Thank you. Could you also point out the possible cause my solution is not producing the intended result?
    – Vishal .R
    Aug 16 at 5:11










  • @Vishal.R Done.
    – Ian
    Aug 16 at 5:12














up vote
0
down vote



accepted










If you use the Euclidean algorithm, the first step can be chosen to be computing $b^n$ mod $a$, then compute $a$ mod that, etc. until you get 0. Then back up a step to get the actual GCD, then finally mod by 1000000007 at the end.



Modding by the final modulus at the start changes the result compared to doing it at the end. For instance consider that gcd(11,4) mod 3 is 1 but gcd(11 mod 3,4) is 2.






share|cite|improve this answer






















  • Thank you. Could you also point out the possible cause my solution is not producing the intended result?
    – Vishal .R
    Aug 16 at 5:11










  • @Vishal.R Done.
    – Ian
    Aug 16 at 5:12












up vote
0
down vote



accepted







up vote
0
down vote



accepted






If you use the Euclidean algorithm, the first step can be chosen to be computing $b^n$ mod $a$, then compute $a$ mod that, etc. until you get 0. Then back up a step to get the actual GCD, then finally mod by 1000000007 at the end.



Modding by the final modulus at the start changes the result compared to doing it at the end. For instance consider that gcd(11,4) mod 3 is 1 but gcd(11 mod 3,4) is 2.






share|cite|improve this answer














If you use the Euclidean algorithm, the first step can be chosen to be computing $b^n$ mod $a$, then compute $a$ mod that, etc. until you get 0. Then back up a step to get the actual GCD, then finally mod by 1000000007 at the end.



Modding by the final modulus at the start changes the result compared to doing it at the end. For instance consider that gcd(11,4) mod 3 is 1 but gcd(11 mod 3,4) is 2.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Aug 16 at 5:11

























answered Aug 16 at 5:07









Ian

65.5k24682




65.5k24682











  • Thank you. Could you also point out the possible cause my solution is not producing the intended result?
    – Vishal .R
    Aug 16 at 5:11










  • @Vishal.R Done.
    – Ian
    Aug 16 at 5:12
















  • Thank you. Could you also point out the possible cause my solution is not producing the intended result?
    – Vishal .R
    Aug 16 at 5:11










  • @Vishal.R Done.
    – Ian
    Aug 16 at 5:12















Thank you. Could you also point out the possible cause my solution is not producing the intended result?
– Vishal .R
Aug 16 at 5:11




Thank you. Could you also point out the possible cause my solution is not producing the intended result?
– Vishal .R
Aug 16 at 5:11












@Vishal.R Done.
– Ian
Aug 16 at 5:12




@Vishal.R Done.
– Ian
Aug 16 at 5:12












 

draft saved


draft discarded


























 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2884408%2fgcd-and-exponentiation-of-large-numbers%23new-answer', 'question_page');

);

Post as a guest
































































-

這個網誌中的熱門文章

How to combine Bézier curves to a surface?

圖片
Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite My aim is to smooth the terrain in a video game. Therefore I contrived an algorithm that makes use of Bézier curves of different orders. But this algorithm is defined in a two dimensional space for now. To shift it into the third dimension I need to somehow combine the Bézier curves. Given two curves in each two dimensions, how can I combine them to build a surface? I thought about something like a curve of a curve. Or maybe I could multiply them somehow. How can I combine them to cause the wanted behavior? Is there a common approach? In the image you can see the input, on the left, and the output, on the right, of the algorithm that works in a two dimensional space. For the real application there is a three dimensional input. The algorithm relays only on the adjacent tiles. Given these it will define the control points of the mentioned Bézier cur...
閱讀完整內容

Mutual Information Always Non-negative

圖片
Clash Royale CLAN TAG #URR8PPP up vote 10 down vote favorite 6 What is the simplest proof that mutual information is always non-negative? i.e., $I(X;Y)ge0$ probability-theory share | cite | improve this question edited Jun 17 '12 at 15:38 Cameron Buie 83.6k 7 71 154 asked Jun 17 '12 at 15:30 Omri 359 3 13 3 Convexity of the function $tmapsto tlog t$. – Did Jun 17 '12 at 15:33 In addition, the convexity properties require the coefficients in the linear combination sum 1. Then, as p(x,y) is a probability distribution, it fullfits such condition. – Francisco Javier Delgado Ceped Aug 10 at 18:44 add a comment  |  up vote 10 down vote favorite 6 What is the simplest proof that mutual information is always non-negative? i.e., $I(X;Y)ge0$ probability-theory share | cite | improve this question edited Jun 17 ...
閱讀完整內容

Why am i infinitely getting the same tweet with the Twitter Search API?

圖片
up vote 0 down vote favorite My code workes perfectly for other queries, but for one query I am infinitely getting the same tweet. I can't understand what the problem is. API call: query='Allergic asthma OR Nonallergic asthma OR Occupational asthma OR EIB OR Exercise-induced bronchoconstriction OR Nocturnal asthma OR Cough-variant asthma' new_tweets = api.search(q=searchQuery, count=100, since_id=since_id, lang='en',tweet_mode='extended') if not new_tweets: print("No more tweets found") break for tweet in new_tweets: if True: print(jsonpickle.encode(tweet._json, unpicklable=False)) my_file = open('searchTweets.txt','a') my_file.write(jsonpickle.encode(tweet._json, unpicklable=False)+'n') my_file.close() else: continue Output in file: https://pastebin.com/JmRCsTeE These are the JSONs of the same Tweet. Other queries that work: Breast cancer OR Prostate cancer OR Colon cancer OR Lung cancer Type 2 dia...
閱讀完整內容