Modulo arthmetic solve for x^N .

  • Context: Undergrad 
  • Thread starter Thread starter shadowhywind
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around solving the equation x^N = a mod b, where participants explore methods and theories related to modular arithmetic. The scope includes theoretical approaches and potential applications in number theory.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested

Main Points Raised

  • One participant expresses difficulty in solving the equation and mentions Fermat's little theorem, noting that b is not prime.
  • Another participant asserts that there is no generic solution to the problem.
  • A suggestion is made to provide specific numbers for clarity in the discussion.
  • One participant recommends researching "nth power residue" for additional resources and references related to the topic.
  • Multiple participants mention the Chinese remainder theorem as a potential method to approach the problem.
  • Another participant suggests factoring b and using Fermat's theorem followed by applying the Chinese remainder theorem to combine results.

Areas of Agreement / Disagreement

Participants have differing views on the existence of a generic solution, with some suggesting methods while others express skepticism about a universal approach. The discussion remains unresolved regarding the best method to solve the equation.

Contextual Notes

Participants have not provided specific assumptions or definitions that may affect the discussion, and the applicability of methods like Fermat's theorem and the Chinese remainder theorem is not fully established in this context.

shadowhywind
Messages
1
Reaction score
0
Modulo arthmetic solve for x^N...

Hay all, I am stuck on a problem, and its driving me crazy. I have a problem, xN = a mod b. Where I have to solve for x. My first thought was use to Fermat's little theorem(if I have the name correct), however my b is not a prime, (neither is 'N' or 'a' for that fact). I can give the exact problem with numbers if needed, but thought it would be slightly easier with variables instead. Any tips on how I could start to solve this would be great. Any questions please ask.
 
Physics news on Phys.org


I believe there is no generic solution to this problem.
 


Giving the actual numbers would probably be best for this one.
 


Google nth power residue for lots of results (and references to specific number theory texts) regarding your question.

Petek
 


Chinese remainder theorem.
 


Hurkyl said:
Chinese remainder theorem.

Yes. Factor b, use Fermat, then CRT the results together.
 

Similar threads

Undergrad Dfns group action & group, written in terms of the other
  • · Replies 26 ·
Replies
26
Views
1K
Undergrad How Do You Determine the Maximum Order of an Element Modulo n?
  • · Replies 10 ·
Replies
10
Views
9K
Undergrad Trouble understanding an online solution to an exercise in Dummit & Foote
  • · Replies 21 ·
Replies
21
Views
2K
Undergrad Understanding the Results of gcd(x,n)
  • · Replies 8 ·
Replies
8
Views
2K
Undergrad Name of distance to nearest multiple of n function?
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Trouble with a passage in Zariski & Samuel's Commutative algebra text
  • · Replies 5 ·
Replies
5
Views
2K
Graduate Structure of modulo-integer matrix group GL(r,Z(n))?
  • · Replies 17 ·
Replies
17
Views
7K
Undergrad Modulo and Modulus in math and computer programming
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Solving a complex linear system with parameters
  • · Replies 11 ·
Replies
11
Views
2K
MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
  • · Replies 3 ·
Replies
3
Views
3K