Any good way to calculate $frac {alpha ^ n - 1 } {alpha - 1} pmod{c}$












4














I tried by multiplying modular inverse of denominator to the numerator and then taking modulo $c$, but there are problems when the inverse does not exist.



So is there a good way to solve this problem.



Constraints
$$ 1 le alpha le 1e9 $$
$c$ is a prime
$$ 1 le n le 1e9 $$






number-theory







share|cite|improve this question









New contributor




satvik choudhary is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • 1




    If $c$ divides $alpha-1$ with multiplicity $k$, you can compute $alpha^n-1pmod{p^{k+1}}$ and then divide by $alpha-1$.
    – Wojowu
    2 days ago
















4














I tried by multiplying modular inverse of denominator to the numerator and then taking modulo $c$, but there are problems when the inverse does not exist.



So is there a good way to solve this problem.



Constraints
$$ 1 le alpha le 1e9 $$
$c$ is a prime
$$ 1 le n le 1e9 $$






number-theory







share|cite|improve this question









New contributor




satvik choudhary is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • 1




    If $c$ divides $alpha-1$ with multiplicity $k$, you can compute $alpha^n-1pmod{p^{k+1}}$ and then divide by $alpha-1$.
    – Wojowu
    2 days ago














4












4








4







I tried by multiplying modular inverse of denominator to the numerator and then taking modulo $c$, but there are problems when the inverse does not exist.



So is there a good way to solve this problem.



Constraints
$$ 1 le alpha le 1e9 $$
$c$ is a prime
$$ 1 le n le 1e9 $$






number-theory







share|cite|improve this question









New contributor




satvik choudhary is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











I tried by multiplying modular inverse of denominator to the numerator and then taking modulo $c$, but there are problems when the inverse does not exist.



So is there a good way to solve this problem.



Constraints
$$ 1 le alpha le 1e9 $$
$c$ is a prime
$$ 1 le n le 1e9 $$






number-theory




number-theory






share|cite|improve this question









New contributor




satvik choudhary is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




satvik choudhary is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited yesterday









rtybase

10.4k21433




10.4k21433






New contributor




satvik choudhary is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 2 days ago









satvik choudhary

215




215




New contributor




satvik choudhary is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





satvik choudhary is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






satvik choudhary is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 1




    If $c$ divides $alpha-1$ with multiplicity $k$, you can compute $alpha^n-1pmod{p^{k+1}}$ and then divide by $alpha-1$.
    – Wojowu
    2 days ago














  • 1




    If $c$ divides $alpha-1$ with multiplicity $k$, you can compute $alpha^n-1pmod{p^{k+1}}$ and then divide by $alpha-1$.
    – Wojowu
    2 days ago








1




1




If $c$ divides $alpha-1$ with multiplicity $k$, you can compute $alpha^n-1pmod{p^{k+1}}$ and then divide by $alpha-1$.
– Wojowu
2 days ago




If $c$ divides $alpha-1$ with multiplicity $k$, you can compute $alpha^n-1pmod{p^{k+1}}$ and then divide by $alpha-1$.
– Wojowu
2 days ago










1 Answer
1






active

oldest

votes


















2














Set $S_0:=1$ and then recursively $S_k:=alpha S_{k-1}+1 pmod c$ for all $k=1,dotsc,n-1$. The last value $S_{n-1}$ is what you seek.






share|cite|improve this answer





















  • Its too slow to be just linearly calculated with n ~ 1e9
    – satvik choudhary
    yesterday










  • A better way would be to go like $ S_k := S_{frac {k}{2}} + alpha ^ {k / 2} S_{k - frac{k}{2}} $
    – satvik choudhary
    yesterday










  • Sure, as long as running time is an issue. (From your question I understood that you are mostly struggling with the situation where the denominator is not invertible.)
    – W-t-P
    16 hours ago











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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});






satvik choudhary is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3060775%2fany-good-way-to-calculate-frac-alpha-n-1-alpha-1-pmodc%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









2














Set $S_0:=1$ and then recursively $S_k:=alpha S_{k-1}+1 pmod c$ for all $k=1,dotsc,n-1$. The last value $S_{n-1}$ is what you seek.






share|cite|improve this answer





















  • Its too slow to be just linearly calculated with n ~ 1e9
    – satvik choudhary
    yesterday










  • A better way would be to go like $ S_k := S_{frac {k}{2}} + alpha ^ {k / 2} S_{k - frac{k}{2}} $
    – satvik choudhary
    yesterday










  • Sure, as long as running time is an issue. (From your question I understood that you are mostly struggling with the situation where the denominator is not invertible.)
    – W-t-P
    16 hours ago
















2














Set $S_0:=1$ and then recursively $S_k:=alpha S_{k-1}+1 pmod c$ for all $k=1,dotsc,n-1$. The last value $S_{n-1}$ is what you seek.






share|cite|improve this answer





















  • Its too slow to be just linearly calculated with n ~ 1e9
    – satvik choudhary
    yesterday










  • A better way would be to go like $ S_k := S_{frac {k}{2}} + alpha ^ {k / 2} S_{k - frac{k}{2}} $
    – satvik choudhary
    yesterday










  • Sure, as long as running time is an issue. (From your question I understood that you are mostly struggling with the situation where the denominator is not invertible.)
    – W-t-P
    16 hours ago














2












2








2






Set $S_0:=1$ and then recursively $S_k:=alpha S_{k-1}+1 pmod c$ for all $k=1,dotsc,n-1$. The last value $S_{n-1}$ is what you seek.






share|cite|improve this answer












Set $S_0:=1$ and then recursively $S_k:=alpha S_{k-1}+1 pmod c$ for all $k=1,dotsc,n-1$. The last value $S_{n-1}$ is what you seek.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 2 days ago









W-t-P

92359




92359












  • Its too slow to be just linearly calculated with n ~ 1e9
    – satvik choudhary
    yesterday










  • A better way would be to go like $ S_k := S_{frac {k}{2}} + alpha ^ {k / 2} S_{k - frac{k}{2}} $
    – satvik choudhary
    yesterday










  • Sure, as long as running time is an issue. (From your question I understood that you are mostly struggling with the situation where the denominator is not invertible.)
    – W-t-P
    16 hours ago


















  • Its too slow to be just linearly calculated with n ~ 1e9
    – satvik choudhary
    yesterday










  • A better way would be to go like $ S_k := S_{frac {k}{2}} + alpha ^ {k / 2} S_{k - frac{k}{2}} $
    – satvik choudhary
    yesterday










  • Sure, as long as running time is an issue. (From your question I understood that you are mostly struggling with the situation where the denominator is not invertible.)
    – W-t-P
    16 hours ago
















Its too slow to be just linearly calculated with n ~ 1e9
– satvik choudhary
yesterday




Its too slow to be just linearly calculated with n ~ 1e9
– satvik choudhary
yesterday












A better way would be to go like $ S_k := S_{frac {k}{2}} + alpha ^ {k / 2} S_{k - frac{k}{2}} $
– satvik choudhary
yesterday




A better way would be to go like $ S_k := S_{frac {k}{2}} + alpha ^ {k / 2} S_{k - frac{k}{2}} $
– satvik choudhary
yesterday












Sure, as long as running time is an issue. (From your question I understood that you are mostly struggling with the situation where the denominator is not invertible.)
– W-t-P
16 hours ago




Sure, as long as running time is an issue. (From your question I understood that you are mostly struggling with the situation where the denominator is not invertible.)
– W-t-P
16 hours ago










satvik choudhary is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















satvik choudhary is a new contributor. Be nice, and check out our Code of Conduct.













satvik choudhary is a new contributor. Be nice, and check out our Code of Conduct.












satvik choudhary is a new contributor. Be nice, and check out our Code of Conduct.
















Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3060775%2fany-good-way-to-calculate-frac-alpha-n-1-alpha-1-pmodc%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

1300-talet

Image
Den här artikeln handlar om hundraårsperioden 1300–1399. För decenniet 1300–1309, se 1300-talet (decennium). .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output ...
Read more

1300-talet

Image
Den här artikeln handlar om hundraårsperioden 1300–1399. För decenniet 1300–1309, se 1300-talet (decennium). .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output ...
Read more

Display a custom attribute below product name in the front-end Magento 1.9.3.8

Image
0 I need to display a custom attribute bellow the product name and I don't know how can I call this attribute. I am editing the file /app/design/frontend/templatemela/MAG100219_1/template/catalog/product/view.phtml But how can I call this attribute in php? I tried calling a string echo with the name I put in the attribute, but it didn't work. Code is as below: <div class="page-title product-title"> <h1><?php echo $_helper->productAttribute($_product, $_product->getName(), 'name') ?></h1> </div> <div class="codigoinmetro"> <h2><?php echo $_helper->productAttribute($_product, $_product->getName(), 'registroinmetro') ?></h2> </div> php attrib...
Read more