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

0
votes
2answers
15 views

Showing Modulo Congruence Amongst Prime Divisors (Number Theory)

I'm having trouble figuring out how to show the general existence part of the following problem. Suppose $n\in\{1,2,3...\}$ and $n\equiv 7\mod{10}$. Show that $\exists$ a prime divisor $p$ of $n$ ...
0
votes
0answers
10 views

Name of that extension of modular inverse?

The modular inverse is a well-defined involution over $\mathbb Z_n^*$: when $\gcd(x,n)=1$, the inverse of $x$ modulo $n$, noted $x^{-1}\bmod n$, is the single integer $z$ with $x\cdot z\equiv1\pmod n$ ...
0
votes
3answers
23 views

What to do if the modulus is not coprime in the Chinese remainder theorem?

Chinese remainder theorem dictates that there is a unique solution if the congruence have coprime modulus. However, what if they are not coprime, and you can't simplify further? E.g. If I have to ...
3
votes
4answers
79 views

Remainder when ${45^{17}}^{17}$ is divided by 204

Find the remainder when ${45^{17^{17}}}$ is divided by 204 I tried using congruence modulo. But I am not able to express it in the form of $a\equiv b\pmod{204}$. $204=2^2\cdot 3\cdot 17$
0
votes
1answer
16 views

What are the values of b such that the matrix [(1,1)(b,1)] is invertible mod 26.

What are the values of b such that the matrix [(1,1)(b,1)] is invertible mod 26. I figured that the matrix is only invertible if its determinant and the n value 26 's gcd is 1, meaning they are ...
0
votes
2answers
30 views

Find a solution $x\in\mathbb{Z_{\mathrm{784}}}$ for $x\cdot\overline{602}=\overline{308}$

I know that I have to find a positive integer $x$ that I can multiply with $602$ and then divide the result by $784$ so that the remainder of that integer division is $308$. I am sure that this is ...
0
votes
2answers
39 views

Solve the following congruence: $x(x+1)(x+2) \equiv 0 \pmod{221}$

Find the first five solutions for, $$x(x+1)(x+2) \equiv 0 \pmod{221}$$ I am very confused. By CRT, $x(x+1)(x+2) \equiv 0 \pmod{13}$ and $x(x+1)(x+2) \equiv 0 \pmod{17}$ But these two ...
4
votes
2answers
79 views

Last digit of $235!^{69}$

Problem What is the last digit of $235!^{69}$? It's been far too long since I did any modulo calcuations, and even then, the factorial would set me back. My initial thought goes to the last digit ...
0
votes
5answers
55 views

How can I prove that $\frac{21n -3}{4}$ and $\frac{15n+2}{4}$ are never both integers?

I have converted this to a problem of modular arithmetic. I seek to prove that $21n-3$ and $15n+2$ are never congruent to $0\pmod 4$ for the same value of $n$. I observed that $21n$ is ...
1
vote
0answers
62 views

Show that the equation $x^2+y^2+z^2= (x-y)(y-z)(z-x)$ has infinitely many solutions in integers $x, y, z$.

Show that the equation $x^2+y^2+z^2= (x-y)(y-z)(z-x)$ has in finitely many solutions in integers $x, y, z$. It seems like if I find a set of $x,y,z$ that satisfy this for any values that will ...
0
votes
0answers
8 views

Stabilizer of a point in R$\cup \infty$ in a discrete subgroup $\Gamma \subset SL_2(R)$

Let $\Gamma $ be a discrete subgroup of $SL_2(R)$. Let $\Gamma_z$={$\gamma \in \Gamma : \gamma(z)=z$}. Let $Z_{\Gamma}$={$\pm I\cap \Gamma$}. Then how to prove for z $\in R\cup \infty$, $\Gamma_z ...
1
vote
1answer
21 views

$A(n) = f(m)$ numbers of $f(m)$ followed by $f(m)$ numbers of $0$. $f(m)$ is the remainder when $m$ is divided by $9$.

A series is formed in the following manner: $A(1) = 1; $ $A(n) = f(m)$ numbers of $f(m)$ followed by $f(m)$ numbers of $0$; $m$ is the number of digits in $A(n-1).$ Find $A(30)$. Here ...
1
vote
2answers
26 views

Find all incongruent solutions to $21x \equiv 14 \pmod{91}$

Find all incongruent solutions to $21x \equiv 14 \pmod{91}$. I am able to work out the solution using Euclidean algorithm techniques, but the signs on the expression do not match up with the initial ...
1
vote
1answer
24 views
1
vote
1answer
36 views

Last 3 digits of Marsenne numbers

Marsenne numbers are of the form $2^{p} - 1$, $p$ is a prime. Last $3$ digits can be obtained from $2^{p} - 1 \equiv x \pmod {1000}$. This is equivalent to $$2^{p} - 1 \equiv x_1 \pmod 8\tag1$$ and ...
0
votes
1answer
23 views

Modulus Notation Division

I have a couple of silly questions (it will definitely demonstrate my lack of ability in mathematics :P) Is there a type of reduction or absorption of modulus in congruence equations? Here's an ...
2
votes
1answer
71 views

How does one prove that $2\uparrow\uparrow16+1$ is composite?

Just to be clear, close observation will show that this is not the Fermat numbers. I was reading some things (link) when I came across the footnote on page 21, which states the following: ...
2
votes
3answers
44 views

Sum of all elements in congruence class modulo n

With $+$ defined as $[a]+[b]=[a+b]$, show that $[0]+[1]+\cdots+[n-1]$ is equal to either $[0]$ or $[n/2]$ in $\Bbb Z_n$. How do I go about proving this? I have managed to get $[(n^2-n)/2]$ using the ...
0
votes
3answers
68 views

Remainder of $98!$ modulo $101$

My question is: What would be the remainder when $98!$ would be divided by $101$? Though this question is very easy but I'm a little confused about my concepts. I have found multiples of $2$ and ...
1
vote
0answers
12 views

Number of Solutions to a Linear Equation Mod N

Is there a formula for the number of solutions to $$a_1x_1+\dots+a_nx_n \equiv 0 \mod{N}$$ such that $(x_i,N)=1$ in terms of the coefficients $a_1,\dots,a_n$? Clearly, by Chinese Remainder Theorem, ...
1
vote
2answers
60 views

$11^{-1}$ modulo $91$ is $58$. Why?

I am reading wiki article about Quadratic Sieve and it says $11^{-1}$ modulo $91$ is $58$ Why? How is it been calculated?
5
votes
1answer
43 views

Modular Arithmetic - summing from 1 to a prime

Apologises for the vague title; I couldn't think of anything better to call it. I'm currently working on the following question: Consider the equation $\sum_{i=1}^{5} \frac{1}{i} = \frac{X}{5Y}$. ...
1
vote
2answers
33 views

Is there a difference between modulo groups with and without asterisks ($\mathbb{Z}_{38}$ vs $\mathbb{Z}_{38}^*$)?

I know modulo group $\mathbb{Z}_{38}$ but I saw it with a star in some question: $\mathbb{Z}_{38}^*$. Is it is the same as $\mathbb{Z}_{38}$ or a different group? If it refers to the same group does ...
-1
votes
0answers
27 views

Do $p=2617$ and $q=3571$ have modular multiplicative inverse with $e = 17$?

I need multiplicative inverse of $17 \mod \left(\phi(p) \cdot \phi(q)\right)$. They are both prime, the totient of the product is $2616 \cdot 3570 = 9339120$. But $17$ is a factor of $9339120$, ...
0
votes
1answer
20 views

Sum of the squares of $5$ consecutive positive numbers can not be a perfect square.

Proof that, Sum of the squares of $5$ consecutive positive numbers can not be a perfect square. As far I did, $(n-2)^2 + (n-1)^2+n^2 + (n+1^2) + (n+2)^2$ $=2(n^2+4) + 2(n^2 + 1) + n^2$ $=5(n^2 + ...
0
votes
5answers
51 views

Is the following proof correct for $n(n+1)(n+5) = 3X$

The objective is to prove that $n(n+1)(n+5)$ is a multiple of 3. I took the following simplistic route $$n(n+1)(n+5) = 3X$$ $$n(n+1)(n+5)\frac{n+2}{n}\frac{n+6}{n+5} = ...
0
votes
0answers
10 views

Using Modulo to calculate number of days to a certain date

I'm trying to create a function that, given today's date and the date of a holiday in day-of-the-year format, returns the number of days between today's date and the date of a holiday. (Day of the ...
1
vote
0answers
28 views

Modular and prime prove [duplicate]

Suppose that $p$ is prime and $p=n^2 +5$ for some natural number $n$, prove that the final digit of $p$ is equal to $1$ or $9$ which is $p=1(mod10)$ or $p=9(mod10)$ What I have to tried so far: in ...
0
votes
1answer
24 views

How can I find the exponent of a power of two from its remainder modulo a power of three?

Suppose that ${2^m}\equiv k\pmod {3^n}$ and that I know $n$ and $k$. Is there a way to find the lowest (or indeed any) value for $m$ other than by enumerating the possibilities? Note: I'm aware that ...
1
vote
1answer
40 views

Find last two digits using modular arithmetic [duplicate]

Find the last two digits of $7^{7^{7^{10217}}}$. We need to find $7^{7^{7^{10217}}}$ (mod $100$) and $\phi(100) = 40$ So $7^{40} \equiv 1$(mod$100$) I don't know how to proceed after this
0
votes
1answer
33 views

Modular exponentiation and two primes

Given two primes $11$ and $5$, find all $\alpha> 1$ such that $$\alpha^{5} \equiv 1 \pmod{11}$$ What theorem will help me to find it out?
0
votes
1answer
16 views

an array A[1..N] how many indexes (i,j) are there such that cumulative sum(i,j)%K = 0?

Lets say I have an array A[x1,x2,x3,...xN] of size N. for N = 4 , A = {x1,x2,x3,x4}. [1 based index] Now,I have to tell how many tuples (i,j) are there such that i<=j and cumulative sum(i,j) is ...
0
votes
2answers
52 views

Solving modulo equations with one variable

Given the following equation: $$10 = 4^x \pmod {18}$$ How can one know what are the correct values for $x$ ?
1
vote
1answer
35 views

How many non-negative integers less than $10000$ are there such that…

I am stuck with the following two problems : How many non-negative integers less than $10000$ are there such that the sum of digits of the number is divisible by $3$ ? The options are : ...
0
votes
0answers
19 views

Calculate large modulus by hand

I want to calculate 920^17 mod 2773. I get 1701 as answer. The answer is 948 in the textbook. It does not explain how to get it. I am using this method: 17 = 1 + 16 (powers of 2) 920^1 mod 2773 = ...
1
vote
0answers
14 views

Cracking any linear congruential generator

I have a linear congruential generator $X_{n+1} = (aX_n + b) \bmod 2^k $with given arguments and number $Y$. The problem is to find the smallest $i$ that $X_i = Y$ or tell that there is no such $i$. ...
3
votes
2answers
40 views

Primitive Root Mod P

I have been able to answer all of the parts to the question apart from part (v). Any tips on how? I assume I have to show that $ m=2^n $, but I am unsure as to how. I can't imagine it is very ...
0
votes
1answer
50 views

Calculating the summation of n mod i

This is a codeforces question (link), where we have to calculate the summation of N mod i where i goes from 1 to M. N and M are very large values 10^13. They have provided an editorial for this ...
0
votes
2answers
31 views

How to compute (10mod42)(17mod42)^-1

Not sure how to tackle this problem since it involves an modular inverse and if I try to treat it as a division, it gives a non-integer solution.
2
votes
3answers
69 views

Some hints for “If a prime $p = n^2+5$, then $p\equiv 1\mod 10$ or $p\equiv 9\mod 10$”

I tried to prove this question by first considering the possible last digit of $p$ when $p=n^2+5$, but that reasoning got me nowhere. Then I tried to prove it by contrapositive, and however I just ...
0
votes
1answer
26 views

Equation solution in modular arithmetic

Given two primes $11$ and $5$, find all $α > 1$ such that $α^{5} \equiv 1 \mod 11$. How would you compute that?
2
votes
1answer
34 views

Find the structure of $\mathbb{Z}_{120}^*$

How to find the structure (in term of cyclic groups) of $\mathbb{Z}_{120}^*$? I know that the number of elements of $\mathbb{Z}_{120}^*= \phi(120) = 32 = 2^5$ But then, any hints?
1
vote
2answers
45 views

Path needed for solving these linear equations in Zn (my example Z105)

So these are two equations : $$49x \equiv 21 \pmod {105}$$ $$64x \equiv 21 \pmod {105}$$ I should find the multiplicative inverse of $64$ and then $49$ that gets the result of $1$ so.... In the ...
0
votes
1answer
27 views

On how many days will Adam and Ben have rest-days on the same day?

Adam and Ben start their new jobs on the same day.Adam's schedule is $3$ workdays followed by $1$ rest day.Ben's schedule is $7$ workdays followed by $3$ rest days.On how many of their fist ...
0
votes
0answers
37 views

Using Chinese Remainder Theorem to find an integer $x$ for which $ x\equiv 3\pmod 4 x\equiv 5\pmod 9 x\equiv 10\pmod {35} $

Hello I have got problems with understanding the reduction method in CRT. We have got system like this $$x\equiv 3\pmod 4$$ $$x\equiv 5\pmod 9$$ $$x\equiv 10\pmod {35}$$ There is a way to do this ...
1
vote
1answer
52 views

Launching a Plaintext Attack against Affine Cipher

Update 2 Being new to the world of Stack Exchange I did not realize that there exists a site solely devoted to cryptography. In light of this, I hope someone could help me migrate this question to ...
-2
votes
1answer
21 views

Show that if [b] and [c] are both multiplicative inverses of [a] in Z_n then b = c(mod n).

I am having some trouble getting started with this problem. I know that I am going to need the following proposition in the proof: Let n > 0 be an integer. Then the following conditions hold for all ...
0
votes
0answers
7 views

Find interval algorithm problem

I have the following arithmetic problem: What is known condition: m,n [a,b) : a mod(m) = 0 , b mod(m) = 0 [x,y) : x mod(n) = 0 , y mod(n) = 0 b < x What must ...
0
votes
0answers
26 views

Let $n\in \mathbb{N}$ and $p>2$ a prime number show that $(1+p)^{p^n} \equiv 1+p^{n+1} \ [p^{n+2}]$

I tried an induction on $n$ : For $n=0$, we obtain : $1+p \equiv 1+p \ [p^2]$ it is right ! For $n=1$, I get : $(1+p)^p = \sum \limits_{k=0}^p \binom pk p^k$ and I noticed that for $k\in ...
0
votes
1answer
16 views

Finding other solutions to diophantine equations

I understand how to find the first solution to these equations but can't grasp how the other solutions are found. E.g. $102x\equiv 12 \pmod{174}$ So I can find the $gcd(174,102)=6$ (showing that ...