How to Find 13 Solutions of ax ≡ 26 (mod 78)

[Shackleford]

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]

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.

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]

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

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]

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.

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

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

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

 

[Dick]

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

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]

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

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

 

[Dick]

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

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

 

[Shackleford]

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

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

 

[Dick]

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

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

 

[Shackleford]

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

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

 

[Dick]

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

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

 

[Shackleford]

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

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?

 

[Dick]

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.

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.

 

[Shackleford]

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?

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]

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.

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]

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?

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]

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.

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

 

[Shackleford]

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

Thanks again for the help!