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

• Shackleford
Thanks again for the help!In summary, the conversation discusses finding the values of a (mod 78) that will result in exactly 13 solutions for the equation ax ≡ 26 (mod 78). It is noted that a solution exists if gcd(a, n) | b and that the largest prime factor of 78 is 13. It is concluded that a = 13n, where n is not divisible by 2 or 3, will satisfy the equation. The conversation ends with well wishes for an upcoming midterm and a tropical storm.
Shackleford

Homework Statement

For what values of a (mod 78) will ax ≡ 26 (mod 78) have exactly 13 solutions?

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.

Shackleford said:

Homework Statement

For what values of a (mod 78) will ax ≡ 26 (mod 78) have exactly 13 solutions?

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

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

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.

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.

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

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

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

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

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

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

Shackleford said:
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.

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

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

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

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

Dick said:
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.

Shackleford said:
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##?

Dick said:
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?

Last edited:
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.

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.

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?

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.

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.

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?

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?

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.

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.

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

Dick said:
Ok, good luck with the midterm and the tropical storm!

Thanks again for the help!

What is the equation for finding 13 solutions of ax ≡ 26 (mod 78)?

The equation is ax ≡ 26 (mod 78), where a is an integer representing the coefficient of x.

What is the process for finding the 13 solutions?

The process involves using the extended Euclidean algorithm to find the inverse of a modulo 78, and then using this inverse to find the 13 solutions by multiplying it with 26.

What is the extended Euclidean algorithm?

The extended Euclidean algorithm is a method used to find the greatest common divisor (gcd) of two integers and their corresponding coefficients, which can be used to find the inverse of a modulo m.

How do you use the extended Euclidean algorithm to find the inverse of a modulo 78?

You can use the extended Euclidean algorithm to find the inverse of a modulo 78 by setting up a table with the values of a, 78, and the coefficients of a and 78 (which are initially 1 and 0, respectively). Then, using the algorithm, you can find the gcd and the corresponding coefficients. The coefficient of a will be the inverse of a modulo 78.

What are the 13 solutions of ax ≡ 26 (mod 78)?

The 13 solutions are x ≡ 2, 14, 26, 38, 50, 62, 74, 86, 98, 110, 122, 134, 146 (mod 78).

• Calculus and Beyond Homework Help
Replies
11
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
876
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
6
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
5K
• Calculus and Beyond Homework Help
Replies
1
Views
938
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
1K