The discussion revolves around determining the values of \( a \) (mod 78) for which the congruence \( ax \equiv 26 \) (mod 78) has exactly 13 solutions. The problem involves concepts related to the greatest common divisor (gcd) and its implications for the number of solutions to modular equations.
The discussion is active, with participants providing insights into the nature of the problem and exploring various interpretations. Some participants have suggested specific values of \( a \) and are considering the broader implications of the gcd condition.
Participants note that the problem is constrained by the requirement that \( a \) must be less than 78 and that it should not be divisible by certain primes (2 and 3) to maintain the gcd condition.
Shackleford said:Homework Statement
For what values of a (mod 78) will ax ≡ 26 (mod 78) have exactly 13 solutions?
Homework Equations
gcd, etc.
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.
Dick said: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##.
Shackleford said: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.
Dick said:##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##?
Shackleford said:Yes. If I'm not mistaken, then I can reduce 13x ≡ 26 (mod 78) to 13*1 ≡ 13*2 (mod 78) to 1 ≡ 2 (mod 6).
Dick said: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##.
Shackleford said:Meaning that I can solve the linear congruence x ≡ 2 (mod 6)
Dick said:So can I. But I don't see what that has to do with this problem.
Shackleford said:Good point. Let's see: 13 and 65.
Dick said:Right! I'd feel better if you said why though.
Shackleford said:Eh. I have a hunch that it relates to the linear form of the GCD.
Dick said:A hunch? ##gcd(a,78)=13## tells you what about the prime factorization of ##a##?
Shackleford said: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.
Dick said: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?
Shackleford said: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.
Dick said: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?
Shackleford said: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.
Dick said:Ok, good luck with the midterm and the tropical storm!