1. Limited time only! Sign up for a free 30min personal 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!

Find values of

  1. Jun 15, 2015 #1
    1. The problem statement, all variables and given/known data
    For what values of a (mod 78) will ax ≡ 26 (mod 78) have exactly 13 solutions?

    2. Relevant equations

    gcd, etc.

    3. The attempt at a solution

    A solutions exists if gcd(a,n) | b.

    gcd(a, 78) | b

    Let d = gcd(a, n). If d|b, then ax ≡ b (mod n) has exactly d solutions.

    I want to set d = 13 = gcd(a, 78) and 13 | 78.

    I know this is a simple problem, but I'm obviously missing something.
     
  2. jcsd
  3. Jun 15, 2015 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    So you are trying to find the form of solutions to ##gcd(a,78)=13##? Think about what that means in terms of prime factorizations of ##a##.
     
  4. Jun 15, 2015 #3
    If m is a natural number and p is a prime, then gcd(m, p) = p if p|m or 1 if p does not divide m. 78 = 2 * 3 * 13. If I let p = a = 13, then I think that I have a solution.
     
  5. Jun 15, 2015 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    ##a=13## is certainly one solution. You can check that directly, but isn't the question asking for a characterization of ALL possible values of ##a##?
     
  6. Jun 15, 2015 #5
    Yes. If I'm not mistaken, then I can reduce 13x ≡ 26 (mod 78) to 13*1x ≡ 13*2 (mod 78) to x ≡ 2 (mod 6).
     
    Last edited: Jun 15, 2015
  7. Jun 15, 2015 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Meaning what? What other values of ##a## satisfy ##gcd(a,78)=13##? Are you sure that's the only one? There are lots of them. But you only need the ones less than ##78##.
     
  8. Jun 15, 2015 #7
    Meaning that I can solve the linear congruence x ≡ 2 (mod 6)
     
  9. Jun 15, 2015 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    So can I. But I don't see what that has to do with this problem.
     
  10. Jun 15, 2015 #9
    Good point. Let's see: 13 and 65.
     
  11. Jun 15, 2015 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Right! I'd feel better if you said why though.
     
  12. Jun 15, 2015 #11
    Eh. I have a hunch that it relates to the linear form of the GCD.
     
  13. Jun 16, 2015 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    A hunch? ##gcd(a,78)=13## tells you what about the prime factorization of ##a##?
     
  14. Jun 16, 2015 #13
    I think I know what you're alluding to, and I forgot all about this representation of the GCD in terms of the primes of minimum degree. 13 is the largest prime?
     
    Last edited: Jun 16, 2015
  15. Jun 16, 2015 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Now that's something you should not forget. It's one of the most useful ways to think of the GCD. If you have the prime factorization for two numbers, the GCD selects the smallest exponent for each prime in the two numbers. Remembering? It's even kind of obvious. That will give you a factor that divides both numbers that can't be made any larger.
     
  16. Jun 16, 2015 #15
    Yes, I had to go back to a previous chapter's notes. The largest prime for 78 is 13 and every prime multiple of 13 except the primes in 78 (2 and 3) satisfies gcd(a, 78) = 13.
     
  17. Jun 16, 2015 #16

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, so ##a## must be 13*n, where n is not divisible by 2 or 3. Is that what you are trying to say? If so, do you see how this solves your problem?
     
  18. Jun 16, 2015 #17
    Yes, because then the gcd would not be 13. The homework was due at midnight so I already turned it in. I'm glad that I stayed up because this was helpful. However, I'm hoping that the impending tropical storm will give me a day to study for the midterm on Wednesday.
     
  19. Jun 16, 2015 #18

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Ok, good luck with the midterm and the tropical storm!
     
  20. Jun 16, 2015 #19
    Thanks again for the help!
     
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: Find values of
  1. Find the value of ? (Replies: 11)

  2. Finding the value of a (Replies: 5)

  3. Find the values of a (Replies: 4)

  4. Find the value of A^2 (Replies: 7)

Loading...