# Thread:

1. ## Find remainder with congruence theorem

This is a problem we ran over in class, but I don't fully understand it.

Find remainder when $3^{1000000}$ is divided by 26.

Solution:

$1000000 = (3)(333333)+1$, therefore $3^{1000000} = 3^{(333333)(3)+1} = 3^{333333}(3)$

By using the congruence theorem, we know that if a congruence b, mod n, then a and b would have the same remainder upon being divided by n.

Then it goes that the remainder is 3, but how do you get that?

2. Originally Posted by tttcomrader
This is a problem we ran over in class, but I don't fully understand it.

Find remainder when $3^{1000000}$ is divided by 26.

Solution:

$1000000 = (3)(333333)+1$, therefore $3^{1000000} = 3^{(333333)(3)+1} = 3^{333333}(3)$

By using the congruence theorem, we know that if a congruence b, mod n, then a and b would have the same remainder upon being divided by n.

Then it goes that the remainder is 3, but how do you get that?
Note that $3^3 = 27$ this means that $3^3 \equiv 27 \equiv 1(\bmod 26)$.
Thus, $(3^3)^{333333} \equiv 1^{333333} (\bmod 26)$.
Thus, $3^{999999}\equiv 1(\bmod 26)$
Multiply both sides by $3$ to get your answer.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 11, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9653843641281128, "perplexity_flag": "head"}