Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $b-a$.

learn more… | top users | synonyms

1
vote
3answers
373 views

Simplifying $(p-1)! + (p-2)! + (p-3)! + (p-4)! + (p-5)! \bmod p$

Trying to get the modulus of the five numbers immediately before a prime, added together in there factorial form; I'll call this operation $S(p)$. For example, $$S(p) = ((p-1)! + (p-2)! + (p-3)! + ...
2
votes
1answer
253 views

When is the quadratic congruence $ax^2 + bx +c \equiv 0 \pmod p$ solvable?

I am learning about quadratic congruences and I don't now how to decide, for which $a, b, c$ and $p$ there is a solution of the congruence. Is it sufficient if the discrminant $b^2-4ac$ has a solution ...
0
votes
2answers
64 views

Solving $ax \equiv b \pmod y$ where $a, b, y$ are known, $b \mid a$, and $y$ prime

I want to find $x$ satisfying $ax \equiv b \pmod y$, provided that: $a,y,b$ are known numbers $b \mid a$ $y$ is not prime.
0
votes
0answers
15 views

subsets with predefined sequences

I have a set $N=\{m,m+1,m+2,...,n\}$ And there are some generating functions of the format : $f(x,k) = (x^2 -1) \mod k$, where $k \le \sqrt m$ and $k$ is in the form $(6i+1)$ or $(6i-1)$, $\forall ...
126
votes
1answer
7k views
+100

A variation of Fermat's little theorem

Fermat's little theorem states that for $n$ prime, $$ a^n \equiv a \pmod{n}. $$ The values of $n$ for which this holds are the primes and the Carmichael numbers. If we modify the congruence ...
0
votes
1answer
27 views

The solutions to $x^m \equiv 1 \bmod p$ will all be solutions to $x^{mn} \equiv 1 \bmod p$ for any $n$.

Can you please show the proof of "The solutions to $x^m \equiv 1 \bmod p$ will all be solutions to $x^{mn} \equiv 1 \bmod p$ for any $n$."
2
votes
4answers
123 views

An easy way to calculate $12^{101} \bmod 551$?

We learn about encryption methods, and in one of the exercises we need to calculate: $12^{101} \bmod 551$. There an easy way to calculate it? We know that: $M^5=12 \mod 551$ And $M^{505}=M$ ($M\in ...
0
votes
0answers
21 views

Rabin's cryptography - when the message $M$ isn't coprime to $n = pq$

Say the message $M$ is a product of one of the primes $p$ or $q$, won't the $gcd$ of $M$ and $n$ (the public encryption key) give me $p$ or $q$? say $p = 11$ $q=19$ $n=11*19=209$ and $M=33$. ...
1
vote
3answers
535 views

Simple Property of GCD and Modular Arithmetic

I'm stuck on proving a rather elementary property, as I'm not really sure how to start off the approach. Suppose $g^a\equiv 1$ mod $m$ and $g^b\equiv 1$ mod $m$. Does this imply that ...
-5
votes
1answer
29 views

Number line how to find leap year [on hold]

How can we use the concept of $4n$ to check whether the number is leap year or not $$4n , \space 4n+1, \space 4n+2, \space4n+3$$
2
votes
2answers
188 views

Fermat's little theorem

This is a very interesting word problem that I came across in an old textbook of mine. So I mused over this problem for a while and tried to look at the different ways to approach it but unfortunately ...
0
votes
4answers
92 views

What is the function “mod”

Surfing this site, I have often seen many functions and expressions involving $\bmod$ and I have no clue about its meaning. What does that $\bmod$ mean?
0
votes
1answer
21 views

polynomial modulo for higher degree

Given $f(x) , n, g(x)$ where $g(x)$ is usually of a small degree then if we find $h_1(x)$ such that $f(x)\equiv h_1(x)\mod \{n,g(x)\}$ , Is there any algorithm to find $h_2(x)$ such that $f(x)\equiv ...
2
votes
1answer
500 views

Find an inverse of $a$ modulo $m$ for each of these pairs of relatively prime integers

How would I find the inverse of a given number $a$ modulo $m$, given that $\gcd(a,m)=1$? a) $a = 2$, $m = 17$ $17 = 2 \cdot 8 + 1$ $2 = 1 \cdot 2 + 0$ $1 = 17 - 8 \cdot 2$ <-How do I know ...
0
votes
4answers
36 views

Units digit when there is a power of power

How do you find the units digit in case of an expression like this $$ 7^{8^7} $$ I know how to find the units digit when there is one integer and there is only one power. But how do I find it when ...
-1
votes
2answers
94 views

Showing that $x^{11} \equiv 5 \pmod{47}$ has only solution $x \equiv 15$.

I don't understand the proof. Where did they get the first line from, i.e., $21 \times 11=1+5 \times 46$? Fermat's theorem in my view is $a^{46} \equiv 1 \pmod {47}$.
0
votes
4answers
36 views

How to manually determine big number congruences

How is it possible to determine if the the following congruence is true manually, with resort to a basic calculator? The real problem here is how to do the math with a such big number? $$ 2015^{50} ...
4
votes
1answer
79 views

Find the remainder when the sum is divided by $1000$

Find $S \pmod{1000}$ given: $$S = \sum_{n=0}^{2015} n! + n^3 - n^2 + n - 1$$ $$S_0 = 0! + 0 - 0 + 0 -1 = 0$$ $$S_1 = 1! + 1 - 1 + 1 - 1 = 1$$ $$S_2 = 2! + 8 - 4 + 2 - 1 = 7$$ This isn't ...
1
vote
1answer
31 views

Polynomial function residues

If we use Euclid's representation for integers $n=aq+r$, we can write $n\equiv r \mod q$. We can also write functions similarly, for example $n(x)=a(x)q(x)+r(x)$ and so I imagine we can write ...
0
votes
3answers
28 views

Double modular exponent with Euler-Fermat

$$7^{3^{18}} \pmod{9}$$ Using this formula : $a^{\phi(m)} \equiv 1 \pmod m$ I got $7^6 \equiv 1 \pmod{9}$ and I can write $3^{18}$ as $3^6 \cdot 3^3$ And what are next steps? I got stuck here.
0
votes
0answers
18 views

One dimensional representations of $SL_2(\mathbb{Z}/n\mathbb{Z})$

Someone knows a reference or knows how to calculate the linear character of $SL_2(\mathbb{Z}/n\mathbb{Z})$, for an arbitrary $n$? Thanks
1
vote
4answers
30 views

system of modular equations.

$x\equiv 2\pmod3$ $x\equiv 3\pmod 5$ $x\equiv 7 \pmod{11}$ How can I solve this system for $x$? I've tried all kinds of things using divisibility but no success. Any hints of solutions are greatly ...
1
vote
3answers
31 views

What is the relation between the linear combination and modular arithmetic?

What is the relation between the linear combination and modular arithmetic? The linear combination is in a field and there must be some fundamental relation between them. What is it?
1
vote
3answers
37 views

Smallest divisible repunits

A repunit of length k is a number containing k ones (1, 11, 111...). R(k) is defined to be the repunit of length k. A(n) is the least value of k such that R(k) is divisble by n (assuming gcd(n, 10) ...
6
votes
7answers
191 views

Calculating remainder of $666^{666}$ when divided by $1000$.

I want to calculate the remainder of $666^{666}$ when divided by $1000$. But for the usual methods I use the divisor is very big. Furthermore $1000$ is not a prime, $666$ is a zero divisor in ...
0
votes
0answers
25 views

Does this modulo formula change odds?

Good day, Consider 5 people each choosing a different number between [0 and A] randomly At the end, we add all the numbers: $n_1+n_2+n_3+n_4+n_5 =N$ Then modulo A+1: $W = N \pmod{A+1}$ My ...
4
votes
1answer
58 views

For any $n$ positive integers ($n\geq 5$) exactly 3 or 4 of them are equal to each other modulo $2^m$ for some $m$

How can one prove that for any $n$ distinct positive integers, $n\geq 5$, there exists $m$ such that exactly 3 or 4 of them are equal to each other modulo $2^m$? I tried to prove it for small $n$. ...
0
votes
1answer
19 views

Intervals of integers modulo n

Do the following related concepts appear anywhere in literature? Denoting an "interval" in the integers modulo $n$ by $[i,j] = \{i, i+1, \dotsc, j\}$. For example, in modulo 6, $[5,3] = ...
3
votes
4answers
279 views

What will be the units digit of $7777^{8888}$?

What will be the units digit of $7777$ raised to the power of $8888$ ? Can someone do the math with explaining the fact "units digit of $7777$ raised to the power of $8888$"?
3
votes
2answers
55 views

$9^{123456789} \pmod{100}$ , retrace calculation operation

I have $9^{123456789} \pmod {100}$. I did use Euler's Theorem, and got $\phi = 40$ and therefore I can say $$9^{123456789 \pmod {40}} \pmod {100}$$ this equals $ 9^{29} \pmod {100}$. Then in one of ...
0
votes
5answers
70 views

How can I prove that $4^{2012} \mod 8$ is $0$

Prove that $4^{2012} \mod 8 = 0$ I'm not really sure what rule I should use to prove this.
2
votes
4answers
76 views

Solving $x^2=17\pmod{128}$

I'm attempring to solve a congruence $x^2 \equiv 17\pmod{128}$ but not quite sure how to go about it. I see that $128 = 2^7$, but the Chinese Remainder Theorem doesn't apply to $\gcd > 1$. I found ...
2
votes
1answer
28 views

Modulo calculation with multiple exponents, via CRT

I'm aware that there are already a few questions like this but unfortunately I wasn't able to find an answer yet. $$ (14^{2014)^{2014}} \pmod {60} $$ So I started off by putting the modular in : $$ ...
-1
votes
1answer
40 views

If p is an odd prime, show that $p^2 \equiv 1 \pmod 8 $

If p is an odd prime, show that $p^2 \equiv 1 \pmod 8 $. I know that odd numbers are of the form $2k \pm 1$. Then $p^2=(2k \pm 1)^2= 4k^2 \pm 4k +1$. But it does not help to solve.
-1
votes
2answers
49 views

Is this problem correct? [duplicate]

I have found another problem in my book. I have to prove that $$2^{70}+3^{70}$$ is divisible by 13. But I have proven that $2^{70}\equiv 12 (mod 13)$ and $3^{70}\equiv 3 (mod 13)$ so it is ...
1
vote
2answers
60 views

How can I find the remainder?

How can I find the remainder when $$(12371^{56}+34)^{28}$$ is divided by $111$. I have tried congruences modulo $111$ but without any success.
2
votes
1answer
41 views

Why is $x^{100} = 1 \mod 1000$ if $x < 1000$ and $\gcd (x,1000) = 1$?

Let $U(1000) =$ the multiplicative group of all integers less than and relative prime to $1000$. "Show that for every $x \in U(1000)$ it is true that $x^{100} = 1 \mod 1000$." Been thinking ...
6
votes
6answers
117 views

What are the last two digits of $77^{17}$?

I'm trying to solve current task referenced the following but I stuck at $\displaystyle77^{17}\equiv x\pmod{100}$. As it is described on above link it uses Binomial Theorem. But I read a lot about the ...
3
votes
2answers
53 views

Polynomial ring addition in $\mathbb{Z_{6}}$

I know this is a very simplest question ever. But, I need help with understanding it. So here it goes... Let, $f(x) = \bar{1}+\bar{2}x+\bar{3}x^2$ and $g(x) = \bar{4}+\bar{5}x$ $\in \mathbb{Z_{6}}.$ ...
0
votes
3answers
27 views

binary representation of integers congruent 1 and 3 modulo 4

Let $k=b_nb_{n-1}\ldots b_3b_2b_1b_0$ be the binary representation of an odd positive integer. Prove: If $k\equiv 1 \mod 4$ then $b_1=0$. If $k\equiv 3 \mod 4$ then $b_1=1$. I think that to prove ...
9
votes
0answers
82 views

Generalizing the Pell equation $x^2-61y^2 = 1$

In a table of fundamental solutions $f_1(x,y)$ to Pell equations, $$x^2-dy^2=1\tag1$$ with $d<110$, two will stand out, $$(U_{61})^6 = \big(\tfrac{39+5\sqrt{61}}{2}\big)^6 = x+y\sqrt{61} ...
0
votes
3answers
41 views

Is it true that $x \nmid (q-1) \implies 2^x \not \equiv 1 \mod q$

If $q$ is a prime number, then from little fermat theorem it is known that $$2^{q-1} \equiv 1 \mod q$$ My doubt is that If $x \nmid (q-1)$ then $2^x \not \equiv 1 \mod q$ is true statement or not? ...
-3
votes
2answers
51 views

Why is $a^{-1}$ mod $p$ equal to $a^{p-2}$ mod $p$? [closed]

Why is $a^{-1}$ mod $p$ equal to $a^{p-2}$ mod $p$ in modular arithmetic?
0
votes
2answers
41 views

Let $z \in \Bbb Z_m$, when is $z^2=1$?

Let $z \in \Bbb Z_m$, when is $z^2=1, (z\neq1)$? I know that for $m$ prime, $z=p-1$ is it's own inverse, but what about nonprime $m$? Is $p-1$ the only self inverse element in $\Bbb Z_p$ ?
4
votes
3answers
55 views

Remainder when divided by 9

I'd like help with this question : What is the remainder when $$2^{2} + 22^{2} + 222^{2}+ \ldots + \underbrace{2222...22^{2}}_{49 \text{ times}} $$ is divided by $9$
1
vote
1answer
458 views

Solving a non-linear congruence

How can we solve for $x$, knowing the integer $n$ and the real numbers $a$ and $b$, the following non-linear congruence: $(x+a)^2=-b\pmod{n}$ Specifically in this example: ...
1
vote
4answers
121 views

Final numbers of $2003^{2003}$ and $2003^{2003^{2003}}$

What are the three final numbers of $2003^{2003}$ and $2003^{2003^{2003}}$? Do I use the Chinese Remainder Theorem here, and if so, how?
3
votes
3answers
118 views

Raising $2$ to the power of $2014^ {2013}$ modulo $41$

The question is as follows: $$2^{{2014}^{2013}}$$ Determine its remainder by division with $41$. I know that I need to use $\bmod 41$ and reduce the power somehow to something that can be solved ...
-3
votes
2answers
85 views

Remainder of $2^{2014^{2013}}$ when divided by $41$ [duplicate]

What is the remainder of $2^{2014^{2013}}$ when divided by $41$? The hint I have to use is that $2^{10}\equiv -1\mod 41$. Can I use the Chinese remainder theorem here? And if so, how?
0
votes
1answer
35 views

What are the solutions of the equation $\phi (x) =p$ with p an prime number, x an integer and $\phi $ the Euler function.

What are the solutions of the equation $\phi (x) =p$ with p an prime number, x an integer and $\phi $ the Euler function. I have actually no idea how to start with solving this problem.