# Solve modular equation

## Homework Statement

Find the integer y with both 0 < y < 144 and 35y = 42(mod 144)

## The Attempt at a Solution

Can someone help me get started on this one? I understand that I can reduce it to 5y = 6(mod 144), and then to 5y = 6 + 144... but I'm not sure what to do with that. I mean, can I just do 5y = 150 and then y = 30?

jbunniii
Homework Helper
Gold Member

## Homework Statement

Find the integer y with both 0 < y < 144 and 35y = 42(mod 144)

## The Attempt at a Solution

Can someone help me get started on this one? I understand that I can reduce it to 5y = 6(mod 144), and then to 5y = 6 + 144... but I'm not sure what to do with that. I mean, can I just do 5y = 150 and then y = 30?

If you plug $$y = 30$$ into the original equation, is it true? If so, then you're done.

An interesting question to consider: if instead of 35, the original equation had 36, then your method would fail. Why? Does the equation have a solution in that case?

A more ambitious question: what is a necessary and condition upon k in order for

ky = 42 (mod 144)

to have a solution? Does the answer change if instead of 42 you use some other number between 0 and 143?

I'm a little confused here. So if I plug my answer into the equation and it doesn't work, it means there are no solutions? And I don't know the answer to the second question

I have another one here:

0 < x < 41
19x = 22(mod 41)

You're right, my previous method didn't work. What can I do?

jbunniii
Homework Helper
Gold Member

I have another one here:

0 < x < 41
19x = 22(mod 41)

You're right, my previous method didn't work. What can I do?

Do you know this theorem:

ax = b (mod n)

has a solution if and only if gcd(a,n) divides b.

In this case, gcd(a,n) = 1 since 19 and 41 are relatively prime. So a solution does exist.

Any solution to this equation:

ax + kn = b, where k is any integer

is also a solution to

ax = b (mod n)

There is a well-known algorithm for finding integers x and k that satisfy

ax + kn = b

provided that a solution exists. Are you familiar with it?

No. :(

Last edited:

I'm still stuck on this... can anyone give me a hand?

HallsofIvy
{"ft_lang_label":"__label__en","ft_lang_prob":0.9361949,"math_prob":0.946908,"size":357,"snap":"2022-05-2022-21","text_gpt3_token_len":124,"char_repetition_ratio":0.12181303,"word_repetition_ratio":0.0,"special_character_ratio":0.394958,"punctuation_ratio":0.09756097,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9995024,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-05-22T20:52:55Z\",\"WARC-Record-ID\":\"<urn:uuid:650123f2-91bb-4471-b2bc-3ff0394949d2>\",\"Content-Length\":\"80147\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:e69d3f94-5c89-453a-8d5e-a59029b828a6>\",\"WARC-Concurrent-To\":\"<urn:uuid:90239130-0d3b-4cd0-9b39-d0479b3b4d90>\",\"WARC-IP-Address\":\"104.26.15.132\",\"WARC-Target-URI\":\"https://www.physicsforums.com/threads/solve-modular-equation.313467/\",\"WARC-Payload-Digest\":\"sha1:KXKIJLNXRGAEULV3G5772KN5YSGMKYFZ\",\"WARC-Block-Digest\":\"sha1:JYZNQGRZPN6ARZGNFKORR3QP4LVKFCVY\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-21/CC-MAIN-2022-21_segments_1652662546071.13_warc_CC-MAIN-20220522190453-20220522220453-00142.warc.gz\"}"}