1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular arithmatic exponential

  1. Feb 24, 2013 #1
    determine if the following congruence has an integer solution: 5x + 4 congruent to 5 (mod 100)


    The only way I could envision this working is by trying all of the remainder values of 100, but I don't think that is the way to go considering there is so many. I tried to figure out an equivalency for 5 [itex]\equiv[/itex] x (mod 100) but that got me nowhere as well.

    What's the simple property I'm probably missing here?
     
  2. jcsd
  3. Feb 24, 2013 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    5 divides 100. So if two numbers are congruent mod 100, they are also congruent mod 5.
     
  4. Feb 24, 2013 #3

    pasmith

    User Avatar
    Homework Helper

    What happens if x = 0?
     
  5. Feb 24, 2013 #4

    is that because we can consider the negative remainder as well? I ask because, I always ever looked at it as 100 had to divide 5, not the other way around.





    So I guess then it follows since 5 is congruent to 5 (mod 100) thats the same as 5-5 = 100q where q is any integer.
     
  6. Feb 24, 2013 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You just mean 'q is some integer', not 'any'. But sure x=0 is a solution. Now you want to check if there are any more solutions. If (5^x+4)-5 is divisible by 100, then it's also divisible by 5. Can that happen if x>0?
     
  7. Feb 24, 2013 #6
    I was about to throw my hands up and give up because I've been here plowing away at numerous other questions.....but thinking about it for a second.....since I just showed that (5^x+4)-5 is divisible by 5, I just reduced the amount of values I have to check and doing it mentally......all of my values will end up with a final digit as a 9.....i.e the only value that works is 5.


    Had another question:

    find the smallest natural numbers x and y such that (7^2)x = (5^3)y

    so this is in a chapter about the fundamental theorem of arithmetic....using that idea, I know I can write each of those powers out into a series of primes.....but the primes don't divide each other in any way.
     
  8. Feb 24, 2013 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    7^2 divides (7^2)x. So it must also divide (5^3)y. What does that tell you about y?
     
  9. Feb 24, 2013 #8

    I don't think I follow. How does 7^2 also divide (5^3)y?.....I see that 7^2 divides (7^2)x and same with the other, but how they divide each other isn't sinking in.
     
  10. Feb 24, 2013 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    (5^3)y and (7^2)x are equal. So, of course, if 7^2 divides one, it must divide the other.
     
  11. Feb 24, 2013 #10

    rcgldr

    User Avatar
    Homework Helper

    What's he's asking is what is the smallest value for y so that 7^2 also divides (5^3)y ?
     
  12. Feb 24, 2013 #11
    but isn't that what I'm trying to figure out initially?

    I view it as this: (5^3)y/(7^2) = (7^2)q for some q......

    ==> y = (7^4)q/(5^3)............
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Modular arithmatic exponential
  1. General Arithmatic (Replies: 4)

  2. Modular Inverses (Replies: 2)

Loading...