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 ...
36
votes
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 ...
13
votes
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 ...
13
votes
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 ...
12
votes
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 ...
11
votes
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$ ...
11
votes
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 ...
11
votes
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
11
votes
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 ...
11
votes
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 ...
11
votes
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 ...
10
votes
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. ...
10
votes
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, ...
9
votes
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 ...
9
votes
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$ ...
8
votes
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 ...
8
votes
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 ...
8
votes
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 ...
7
votes
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?
7
votes
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 ...
7
votes
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?
...
7
votes
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 ...
7
votes
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 ...
7
votes
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, ...
7
votes
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 ...
6
votes
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.
6
votes
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) = ...
6
votes
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
$$ ...
6
votes
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 ...
6
votes
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 ...
6
votes
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 ...
6
votes
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, ...
6
votes
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 ...
6
votes
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 ...
6
votes
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 ...
6
votes
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 ...
6
votes
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 ...
6
votes
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 ...
6
votes
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 ...
5
votes
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.
5
votes
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 ...
5
votes
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}$.
5
votes
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. ...
5
votes
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 ...
5
votes
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.
5
votes
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.
5
votes
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.
5
votes
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 ...
5
votes
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$ ...
5
votes
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 ...
5
votes
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.
...
