# Find values of

1. Jun 15, 2015

### Shackleford

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. Jun 15, 2015

### Dick

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$.

3. Jun 15, 2015

### Shackleford

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.

4. Jun 15, 2015

### Dick

$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$?

5. Jun 15, 2015

### Shackleford

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
6. Jun 15, 2015

### Dick

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$.

7. Jun 15, 2015

### Shackleford

Meaning that I can solve the linear congruence x ≡ 2 (mod 6)

8. Jun 15, 2015

### Dick

So can I. But I don't see what that has to do with this problem.

9. Jun 15, 2015

### Shackleford

Good point. Let's see: 13 and 65.

10. Jun 15, 2015

### Dick

Right! I'd feel better if you said why though.

11. Jun 15, 2015

### Shackleford

Eh. I have a hunch that it relates to the linear form of the GCD.

12. Jun 16, 2015

### Dick

A hunch? $gcd(a,78)=13$ tells you what about the prime factorization of $a$?

13. Jun 16, 2015

### Shackleford

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
14. Jun 16, 2015

### Dick

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.

15. Jun 16, 2015

### Shackleford

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.

16. Jun 16, 2015

### Dick

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?

17. Jun 16, 2015

### Shackleford

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.

18. Jun 16, 2015

### Dick

Ok, good luck with the midterm and the tropical storm!

19. Jun 16, 2015

### Shackleford

Thanks again for the help!