# Tagged Questions

Modular arithmetic (clock arithmetic) is a system of arithmetic of integers. The basic ingredient is the congruence relation $a \equiv b \bmod n$ which means that $n$ divides $b-a$. In modular arithmetic one can add, subtract, multiply and exponentiate but not divide in general. The Euclidean ...

14answers
2k views

### 'Linux' math program with interactive terminal?

Are there any open source math programs out there that have an interactive terminal and that work on linux? So for example you could enter two matrices and specify an operation such as multiply and ...
6answers
558 views

### Show that $\frac{(3^{77}-1)}{2}$ is odd and composite

The question given to me is: Show that $\large\frac{(3^{77}-1)}{2}$ is odd and composite. We can show that $\forall n\in\mathbb{N}$: 3^{n}\equiv\left\{ \begin{array}{l l} 1 & \quad ...
2answers
296 views

### Find a composite number $n$ satisfies $(2+3I)^n≡2-3I\pmod{n}$

As we know if $p$ is an odd prime number then $$(a+bI)^p\equiv a+(-1)^\frac{p-1}2bI\pmod{p},$$ where $I=\sqrt{-1}$. However, is there any composite number $n$ that satisfies ...
2answers
239 views

### A puzzle with powers and tetration mod n

A friend recently asked me if I could solve these three problems: (a) Prove that the sequence $1^1, 2^2, 3^3, \dots \pmod{3}$ in other words $\{n^n \pmod{3} \}$ is periodic, and find the length of ...
2answers
461 views

### nth powers modulo all primes

Let $a \in \mathbb{Z}$, $n \in \mathbb{N}^*$ be integers, and set $P=X^n - a$. Let us consider the three following statements : 1) $P$ has a root in $\mathbb{Z}$ (i.e. $a$ is an nth power) 2) $P$ ...
5answers
193 views

### Why are there$736$ $2\times 2$ matrices $(M)$ over $\mathbb{Z}_{26}$ for which it holds that $M=M^{-1}$?

I'm currently trying to introduce myself to cryptography. I'm reading about the Hill Cipher currently in the book Applied Abstract Algebra. The Hill Cipher uses an invertible matrix $M$ for ...
1answer
7k views

### Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly? Thanks
2answers
194 views

### Solve congruence: $45x \equiv 15 \pmod{78}$ (What am I doing wrong?)

Question about solving congruence. I've worked out how to solve them for the most part except for the following problem I'm having: $$45x \equiv 15 \pmod{78}$$ By the euclidean algorithm, I work out ...
3answers
2k views

### Calculate which day of the week a date falls in using modular arithmetic

In Summer Wars the main character (he is a mathematician) calculates the day of the week of someone's birthday (19/07/1992 is Sunday). I know (very) basic modular arithmetic but I can't figure out how ...
2answers
157 views

### Is my shorter expression for $s_m(n)= 1^m+2^m+3^m+\cdots+(n-1)^m \pmod n$ true?

I'm considering the following sums for natural numbers n,m $$s_m(n)= \sum_{k=1}^{n-1} k^m =1^m+2^m+3^m+\cdots+(n-1)^m$$ modulo n . Looking at odd n first, I found by analysis of the pattern of ...
5answers
1k views

### If $n$ is composite, then $n$ divides $(n-1)!$.

I have a proof and need some feedback. It seems really obvious that the statement is true but it is always the obvious ones that are a little trickier to prove. So I would appreciate any feedback. ...
2answers
226 views

### Formula for occurrence of leap years in the Jewish calendar

Over at Judaism.SE, there was a discussion about a formula to determine leap years in the Jewish calendar. Basically, the calendar follows a 19-year cycle, and seven of those years -- 3, 6, 8, 11, 14, ...
7answers
654 views

### Pattern to last three digits of power of $3$?

I'm wondering if there is a pattern to the last three digits of a a power of $3$? I need to find out the last three digits of $3^{27}$, without a calculator. I've tried to find a pattern but can not ...
1answer
158 views

### Elementary Number Theory; prove existence

Prove that there exists a positive integer $n$ such that $$2^{2012}\;|\;n^n+2011.$$ I was wondering if you could prove this somehow with induction (assume that $n$ exists for $2^k|n^n+2011$ ...
2answers
441 views

### The modular curve X(N)

I have a question about the modular curve X(N), which classifies elliptic curves with full level N structure. (A level N structure of an elliptic curve E is an isomorphism from $Z/NZ \times Z/NZ$ to ...
2answers
583 views

### Very simple question, but what is the proof that x.y mod m == ((x mod m).y) mod m?

I apologise for this question, as it is no doubt very simple, but I've never been very confident with proofs. Our lecturer today (in a course related to maths but not mathematical itself) was playing ...
1answer
403 views

### Why are the only numbers $m$ for which $n^{m+1}\equiv n \pmod{m}$ is true also unique for $\displaystyle\sum_{n=1}^{m}{n^m}\equiv 1 \bmod m$?

It can be seen here that the only numbers for which $n^{m+1}\equiv n \pmod{m}$ is true are 1, 2, 6, 42, and 1806. Through experimentation, it has been found that ...
3answers
164 views

### Why do the gaussian integers have only 2 congruence classes mod 1+i?

If we consider $Z[i]$ modulo $1+i$, why are there only two congruence classes?
4answers
329 views

### A “fast” way to manually compute $3^{41}+7^{41} \pmod{13}$

The problem: Find the remainder of $3^{41}+7^{41}$ when divided by $13$. My approach is by utilizing the cyclicity of remainders for examples $3^1,3^2,3^3,3^4,3^5 \text{ and }3^6$ when divided ...
2answers
208 views

### $3x^2 ≡ 9 \pmod{13}$

What is $3x^2 ≡ 9 \pmod{13}$? By simplifying the expression as $x^2 ≡ 3 \pmod{13}$ and applying brute force I can show that the answers are 4 and 9, but how to approach this in a more efficient way? ...
3answers
392 views

### How to find the solutions for the n-th root of unity in modular arithmetic?

$$\begin{align*} x^n\equiv1&\pmod p\quad(1)\\ x^n\equiv-1&\pmod p\quad(2)\end{align*}$$ Where $n\in\mathbb{N}$,$\quad p\in\text{Primes}$ and $x\in \{0,1,2\dots,p-1\}$. How we can find the ...
3answers
207 views

### Number of integers not divisible by $p$ and $q$

Here's a part of question from Siklos' "Advanced Problems in Core Mathematics": How many integers greater than or equal to zero and less than 1000 are not divisible by 2 or 5? What is the average ...
4answers
237 views

### A solution to $y^5 \equiv 2\pmod{251}$

I need to show that the following equation has a solution. (I am not asked for the answer, which I know by Mathematica to be $y=43$. ) $y^5 \equiv 2 \pmod{251}.$ I know that the order of 2 is 50, ...
1answer
265 views

### Is there formal name and proof for this formula/theorem (for now I'm calling it Orbital Collinearity Theorem)?

Suppose you are given a question that goes like this: Consider three planets that revolve around a star on separate circular orbits sharing the same orbital plane. The first planet, A, takes ...
5answers
315 views

### Basic question about mod

I'm having a tough time understanding why $(a^x \bmod p)^y \bmod p$ is equal to $a^{xy}\bmod p$. Does this have a mathematical proof? Please advise.
4answers
263 views

### How can I show $e^2 \equiv 1 \bmod 24$, given that $\gcd(e, 24) = 1$?

The problem comes from a practice final for a final exam I have later today. It says "Show that if $\gcd(e, 24) = 1$ then $e^2 \equiv 1 \bmod 24$". I found that Euler's totient function \$\phi(24) = ...
4answers
2k views

### Modular exponentiation using Euler’s theorem

How can I calculate $27^{41}\ \mathrm{mod}\ 77$ as simple as possible? I already know that $27^{60}\ \mathrm{mod}\ 77 = 1$ because of Euler’s theorem: $$a^{\phi(n)}\ \mathrm{mod}\ n = 1$$ and  ...
4answers
485 views

### calculating n choose k mod one million

I am working on a programming problem where I need to calculate 'n choose k'. I am using the relation formula $${n\choose k} = {n\choose k-1} \frac{n-k+1}{k}$$ so I don't have to calculate huge ...
6answers
124 views

### Number Theory and Congruency

I have the following problem: $$2x+7=3 \pmod{17}$$ I know HOW to do this problem. It's as follows: $$2x=3-7\\ x=-2\equiv 15\pmod{17}$$ But I have no idea WHY I'm doing that. I don't really even ...
3answers
216 views

### Find $n\geq1$ such that 7 divides $n^n-3$

Find $n\geq1$ such that 7 divides $n^n-3$. Here is what I found: $n\equiv 0 \mod7, n^n\equiv 0 \mod7,n^n-3\equiv -3 \mod7$ no solution. \$ n\equiv 1 \mod7, n^n\equiv 1 \mod7,n^n-3\equiv -2 \mod7 ...
4answers
453 views

### How do I compute $a^b\,\bmod c$ by hand?

How do I efficiently compute $a^b\,\bmod c$: When $b$ is huge, for instance $5^{844325}\,\bmod 21$? When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, ...
3answers
143 views

### Number of $k^p \bmod q$ classes when $q\%p > 1$

I want to show that when $p, q$ are primes, $k^p\bmod q$ takes on $q-1$ distinct values (as $k$ ranges over positive integers) if and only if $q \not\equiv 1 \pmod p$. (It is easy to verify this ...
2answers
282 views

### Find all linearly dependent subsets of this set of vectors

I have vectors in such form (1 1 1 0 1 0) (0 0 1 0 0 0) (1 0 0 0 0 0) (0 0 0 1 0 0) (1 1 0 0 1 0) (0 0 1 1 0 0) (1 0 1 1 0 0) I need to find all linear ...
1answer
62 views

### Is there always a primitive m-th root of unity with imaginary part bigger than 1/2

Let $m$ be a positive integer. I need the existence of a primitive $m$-th root of unity $\zeta_m$ such that its imaginary part is strictly greater than $1/2$. We can write \$\zeta_m = \exp(2\pi i ...
2answers
495 views

### Tribonacci sequence modulo X

The Tribonacci sequence satisfies $$T(n) = T(n-1) + T(n-2) + T(n-3)$$ with $T(0)=0$, $T(1)=1$, $T(2)=1$. I need to calculate $T(y) \mod 10000$ for $y > 2^{40}$. How can I make this faster? I ...
1answer
86 views

### Tell wether $(1234657)! +1 \equiv_{11111} (7654321)! -1$ is true or false

I have to tell if the following is true or false: $$(1234657)! +1 \equiv_{11111} (7654321)! -1$$ so by definition we can rewrite the previous equivalence as: \$(1 \cdot 2 \cdot \ldots \cdot 11110 ...
1answer
437 views

### Modular arithmetic problem

I need some hints for this problem from Dummit and Foote. (edit: added the full question verbatim for context) Let $p$ be an odd prime and let $n$ be a positive integer. Use the binomial theorem to ...
1answer
108 views

### A proof in number theory dealing with modular congruences.

So we are asked to show that $$(p-1)(p-2)\cdots(p-r)\equiv (-1)^{r}r! \pmod{p}$$ for $r=1,2,...,p-1$. I worked on it and I want to know if my proof suffices to show what is being asked. I would also ...
5answers
209 views

### Proving that $2^{2^n} + 5$ is always composite by working modulo 3

By working modulo 3, prove that $2^{2^n} + 5$ is always composite for every positive integer n. No need for a formal proof by induction, just the basic idea will be great.
3answers
222 views

### How can I prove that an order (“$<$” say) on $\mathbb Z_n$ cannot be defined?

I'm trying to show why it isn't possible to define an order of magnitude on $\mathbb Z_n$ (modular arithmetic) that satisfies the ordering properties of $\mathbb Z$. By letting addition to be ...
5answers
250 views

### How to solve $100x +19 =0 \pmod{23}$

How to solve $100x +19 =0 \pmod{23}$, which is $100x=-19 \pmod{23}$ ? In general I want to know how to solve $ax=b \pmod{c}$.
5answers
209 views

### Why is $x^2 \pmod{16}$ always $0, \ 1,\ 4,\ 9$?

With a simple piece of code I could deduce that for any non-negative integer $x$ the value of $x^2 \pmod{16}$ is always a number from the set $\{0, 1, 4, 9\}$. However, the math behind it evades me. ...
6answers
134 views

### Show that $x^4 +1$ is reducible over $\mathbb{Z}_{11}[x]$ and splits over $\mathbb{Z}_{17}[x]$.

Reduction into linear factors $\mathbb{Z}_{17}[x]$: This part is not too hard: $x^4 \equiv -1$ mod 17 has solutions: 2, 8, 9, 15 so \$(x-2)(x-8)(x-9)(x-15) = x^4 -34 x^3 +391 x^2-1734 x+2160 \equiv ...
3answers
216 views

### How to compute $7^{7^{7^{100}}} \bmod 100$?

How to compute $7^{7^{7^{100}}} \bmod 100$? Is $$7^{7^{7^{100}}} \equiv7^{7^{\left(7^{100} \bmod 100\right)}} \bmod 100?$$ Thank you very much.
2answers
129 views

### How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?

How to prove $\forall m,n\in\mathbb N$: $$56786730 \mid mn(m^{60}-n^{60})?$$ Thanks in advance.
4answers
999 views

### How do you calculate the modulo of a high-raised number?

I need some help with this problem: $$439^{233} \mod 713$$ I can't calculate $439^{223}$ since it's a very big number, there must be a way to do this. Thanks.
2answers
139 views

### $(1+p)^n$ is not $1 \pmod {p^r}$ when $n < p^{r-1}$

Let $p$ be an odd prime. I know that $(1+p)^{p^{r-1}}\equiv 1 \pmod {p^r}$ but how can I prove that if $n < p^{r-1}$ then $(1+p)^n$ is not $1 \pmod {p^r}$. I tried to prove using the properties of ...
2answers
157 views

### Efficient way to find $a$ in $c = 6a\mod n$

Given $c$ and $n$ in $c = 6a\mod n$, how can I find the lowest positive integer value for $a$? I could find it iteratively by rewriting as $\displaystyle a = \frac{c + xn}{6}$ and increasing $x$ ...
3answers
435 views

### How to calculate $3^{45357} \mod 5$?

I wrote some code, here is what it gives: \begin{align*} 3^0 \mod 5 = 1 \\ 3^1 \mod 5 = 3 \\ 3^2 \mod 5 = 4 \\ 3^3 \mod 5 = 2 \\\\ 3^4 \mod 5 = 1 \\ 3^5 \mod 5 = 3 \\ 3^6 \mod 5 = 4 \\ 3^7 \mod 5 = 2 ...
4answers
57 views

### $20^{15} + 16^{18}$ is divided by 17

What is the reminder, when $20^{15} + 16^{18}$ is divided by 17. I'm asking the similar question because I have little confusions in MOD. If you use mod then please elaborate that for beginner. ...
{"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": 147, "mathjax_display_tex": 15, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "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.932000994682312, "perplexity_flag": "head"}