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
30 views

In modular arithmetic is $m^{1/x}$ =! $(m^x)^{-1}$

In modular arithmetic is $m^{1/x}$ =! $(m^x)^{-1}$ as we always use inverse instead of reverse in multiplicative group.why reverse operation is not used in modular arithmetic and if one want to use ...
3
votes
2answers
608 views

Frog Jump Problem

Lotus leaves are arranged around a circle. A Frog starts jumping from one leaf in the manner described below. In the first jump it skips one leaf,next jump it skips two,three the next jump ...
1
vote
2answers
55 views

Show that there exists no integer coordinates on curve

Problem: Show that there does not exist any integer coordinates to the curve $$y = \frac{x^2-3}{4}, x\in \mathbb{R}.$$ My attempt: The problem is equivalent of saying that there does not exist any ...
0
votes
1answer
22 views

Property of modulo congruation

If I have: $$a^b \equiv 1 \mod xy$$ where $x,y$ are primes, is then true that: $$ a^b \equiv 1 \mod x$$ $$ a^b \equiv 1 \mod y$$ I don't sure if this is true, because I don't know how can I prove it ...
0
votes
1answer
81 views

The addition table for $\mathbb Z/4$ - modular arithmetic

"Write down the addition table for $\mathbb Z/4$ " Could someone please give one or two hints? And what does them mean with $\mathbb Z/4$? They have never used that notation before. Do them just mean ...
3
votes
3answers
68 views

$\operatorname{lcm}(n,m,p)\times \gcd(m,n) \times \gcd(n,p) \times \gcd(n,p)= nmp \times \gcd(n,m,p)$, solve for $n,m,p$?

$\newcommand{\lcm}{\operatorname{lcm}}$ I saw this in the first Moscow Olympiad of Mathematics (1935), the equation was : $$\lcm(n,m,p)\times \gcd(m,n) \times \gcd(n,p)^2 = nmp \times \gcd(n,m,p)$$ ...
0
votes
3answers
26 views

unique solution for mod equation

If I have these equations $a\equiv b \pmod c$ $d\equiv e \pmod c$ All known except $c$ and $\gcd(b−a,e−d)=1$ how do I find the unique solution for $c$? and if the gcd!= 1 how do I find some ...
1
vote
0answers
80 views

Help for solving quadratic residue.

I am solving CRYPTO1 problem. This problem requires to solve following equation: $$x^2=q(\mod p)$$ where I am given $p=4,000,000,007$ and q is also given. I followed ...
0
votes
1answer
47 views

question about the forms of prime numbers

I was thinking about primes earlier and I thought of a hypothesis that I have been unable to prove. I was wondering whether it was a known theorem and whether anyone knows a proof or can prove (or ...
0
votes
1answer
30 views

Can we define the equality as $a=b$ iff $\frac{a}{b}=1$?

Well, The title i guess is enough to get what i'm looking for: I'm wondering if we can define equality of let's say $a$ and $b$ that the devision of $a$ over $b$ or $b$ over $a$ is $1$ : $$a=b ...
0
votes
2answers
67 views

Can we say that $a=b \implies a \equiv b \pmod{0}$?

I'm wondering if we can write $a=b$ as $a \equiv b \pmod{0}$. Because the last congruence satisfies $b-a=0\times k$ $\implies b-a=0$. Which is really $b=a$.
0
votes
1answer
78 views

Public Key Scheme decryption. [closed]

You have been sent a message based on the following Public Key Scheme. 1) Bob chooses two large primes $\ p,q $ with $ p \equiv q \equiv 2 \pmod 3$ and computes $ n=pq. $ 2) Bob chooses integers $ e,d ...
1
vote
0answers
178 views

Solving the discrete logarithm using index calculus, finite fields and factor bases.

(a) Let $p$ be the prime 1073741827, with $\Bbb{F}_p$ the corresponding finite field. A primitive root in $\Bbb{F}_p$ is equal to $g=2$. Use a factor base of primes up to 13 to find the discrete ...
0
votes
2answers
94 views

Count subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively

Given a set of N elements, compute the number of subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively. Any hints would be appreciated. Thanks!
1
vote
1answer
84 views

Solution set to exponential in congruence

For which $n>0$ does $x^{2^n} \equiv 7 (mod \ 9)$ have a solution? It might be useful to start $x^{2^n} \equiv 16 (mod \ 9)$ but how should one proceed? Any hints would be appreciated. Thanks!
0
votes
1answer
47 views

A form of Chinese remainder theorem

How can we solve equations of the form $c \equiv a \mod b$ for finding the c? Also, sometimes $c$ can be two different numbers, one negative and one positive, when is that possible and how does it ...
0
votes
3answers
49 views

Define a relation on $Z$ by a~b if and only if $a=b(mod2)$ and $a=b(mod5)$. Show that ~ is an equivalence relation.

The if and only if is throwing me off. Would the first direction be to prove the two modular conditions hold if the relation is an equivalence relation? Furthermore, I'm having difficulty proving ...
3
votes
5answers
70 views

Solve $85x \equiv 34 \pmod{153}$

I'm not exactly sure how to solve these modular problems involving a variable. Can someone solve this (trivial) example with explanation? I found the answer (4) by trial and error, however, I'm sure ...
-1
votes
2answers
65 views

Find the natural numbers $n$ in which $n^2$ divides $584$? [duplicate]

I'm trying to find the natural numbers $n$ in which $n^2$ divides $584$ ? i tried all the ways i know but i get stuck.
0
votes
1answer
50 views

Finding discrete maps with prescribed cycle-structure (functional digraph-structure)

I apologize in advance for the naive nature of the following questions. I am also thankful to suggestions for improving the direction of the questions instead of direct answers. Let $f: \mathbb N \to ...
6
votes
2answers
325 views

Sum of Digits Question

If A is the sum of the digits of $5^{10000}$, B is the sum of the digits of A, and C is the sum of the digits of B, what is C? I know it has something to do with mod 9, but I'm not sure how do use it ...
2
votes
2answers
121 views

Olympiad Modulo Problem

I have begun preparing for the British Mathematical Olympiad and hope to do well. However, I have been working on the first problem in the book: A Mathematical Olympiad Primer by Geoff Smith, captain ...
1
vote
0answers
49 views

Sigma notation using Modulo

I've come across a step in a proof in a book on number theory that doesn't make sense to me: $$\sum_{n(mod\,p)}\frac{n(n-1)(n+1)}{p}$$ $$=\sum_{n(mod\,p)}\frac{(n+1)(n)(n+2)}{p}$$ As I understand ...
-3
votes
3answers
225 views

Congruence $x^n\equiv2 \pmod{13}$ (Multiple Choice)

I was trying to solve the following problem.Please help. Consider the $x^n\equiv2 \pmod{13}$. It has a solution for $x$ if $n=5$ $n=6$ $n=7$ $n=8$ It may have more than one correct options. Thnx ...
1
vote
4answers
120 views

Formula for Modulo

What is the formula for modulo (finding the remainder of a division). In programming, the symbol used is generally %. 2%2 = 0 3%2 = 1 5%3 = 2 7%4 = 3 Edit: I ...
2
votes
1answer
30 views

Solve for b when $44 \equiv 7 ^ b \pmod{71}$

How do I solve for $b$? $$44 \equiv 7 ^ b \pmod{71}$$ I can only get as far as: $$44 \cdot7^{-1} \equiv b\pmod{71}$$ Although I'm not even sure that that's right.
0
votes
1answer
86 views

Complex modulus? No, not the absolute value.

I was trying to make a class for complex numbers (VB.NET) but then I stumbled upon a problem. How do I define the $mod$ operator for Complex numbers? First I asked Wolfram Alpha. It didn't help much. ...
-1
votes
3answers
82 views

mod of minus power 1

I am fully aware on how to perform mod calculation. The issue now is that when I have this $2^{-1} \bmod 10$. How to do this? Is there any formula for this?
0
votes
1answer
52 views

Solving two variables system equations with parameter above $\mathbb{Z}_7$

Let: $$(1+5a)x +y = 1$$ $$a^2x + y = 2$$ Eliminating the $y$ variable we have: $$(-a^2 +5a +1)x = 6$$ Now, I should have find $y$ such that $(-a^2 +5a +1)y = 1$, but obvoiusly I can't do that ...
2
votes
3answers
123 views

Modular congruence, splitting a modulo

I can't find out, how to solve this. Will you give me some advice what to do in 4th step? Lot of thanks. This is my example: $7^{30}\equiv x\pmod{ 100}$ I want to compute it this way. These are my ...
1
vote
1answer
75 views

What does $ a \pmod b$ mean?

I am having little trouble in what a$mod$b means. I under stand that if $a\equiv b\pmod n$, then n divides (a-b). But I do not understand what does it mean by $b\pmod n$. One the thing I can think of ...
1
vote
1answer
47 views

Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$

I have a workbook question that doesn't have any example solution, that is as follows: Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$ Now I can see $\phi(11)=10$ and $2$ has order $10$ ...
3
votes
3answers
65 views

Solve for x in $5 \equiv 128x$ (mod 59)

I'm just running a blank here in review for finals and cannot seem to figure it out for the life of me. I want to say that you must use extended euclidean algorithm somehow, and I checked that the ...
2
votes
2answers
366 views

Show that an integer of the form $8k + 7$ cannot be written as the sum of three squares.

I have figured out a (long, and tedious) way to do it. But I was wondering if there is some sort of direct correlation or another path that I completely missed. My attempt at the program was as ...
1
vote
3answers
126 views

Verify that $4(29!)+5!$ is divisible by $31$.

Verify that $4(29!)+5!$ is divisible by $31$ I know I have to use Wilsons theorem: $(p-1)!=-1\pmod p$ but I'm not really sure how to apply this theorem. Step by step explanation please? Thank you!
0
votes
1answer
61 views

What day of the week was it on this date in the year 1000?

Don't forget that every year divisible by 4 is a leap year, except that century years are only leap years if divisible by 400 (e.g., 2000 was a leap year, but 1900 was not). Another question in my ...
0
votes
0answers
64 views

Why there is no zero-divisors modulo a prime.

Let us say that an integer $k$ where $0< k < m$ is a zero-divisor mod $m$ if $kn \equiv 0 \pmod{m}$ for some $n$ with $0 < n < m$. Prove the following: If $m$ is prime then no integer $k$ ...
0
votes
0answers
38 views

About gaussian integers and orders.

I noticed $(1+i)^{16}= 256$ so $(1+i)^{16} - 1$ is a multiple of $17$. So $(1+i)^{16} - 1$ is a multiple of $(1+4i)$ or $(1-4i)$. $(1+i)^{|1+4i|}$ is congruent to $1$ or $i$ mod $(1+4i)$. I think . ...
0
votes
1answer
17 views

Solving for modular expression?

I stuck somehow on repetition old math exercises...could someone explain the following expression: $(n!-1)$ mod $ n $ Thanx
0
votes
3answers
51 views

Modular equations, find x

Problem: Find an integer $x$ such that $x = 5\pmod 8, x = 3 \pmod 9, x = 4 \pmod 7$. Attempt: By the Chinese Remainder Theorem " Suppose $a_1,a_2,...a_k$ are integers pairwise relatively prime ...
1
vote
3answers
55 views

Modulo Inverse using extended euclidean

My aim here to learn the Chinese Remainder theorem. But am stuck at finding the inverses. Suppose we have 42 mod 5, but according to the CRT question, we must make it 42 * x congruent to 1 (mod 5) ...
0
votes
1answer
54 views

Given the gcd(a, b) = 1, prove x = y mod a & x = y mod b iff x = y mod a*b

I am thinking that this is a variation of the Chinese Remainder Theorem as the iff qualifies that this set of equations is not exactly the definition of the Chinese Remainder Theorem, leading me to ...
2
votes
2answers
90 views

Modulus simplification $(mn) \bmod d = ab$?

I have a modulus question that needs me too prove whether two different statements are true or false. The information I have been given is that: \begin{align} m \bmod d &= a\\ n \bmod d &= ...
1
vote
2answers
194 views

find smallest value of N such that N mod 10 = 9 , N mod 9 = 8 and so on

find the smallest value of N such that N mod 10=9, N mod 9 = 8, N mod 8 = 7, N mod 7 = 6 and so on till N mod 2 = 1 .
0
votes
2answers
23 views

For what values of b does the following system of modular equations have a solution?

$$x \equiv b (100)$$ $$x \equiv b^2 (35)$$ $$x \equiv 3b - 2 (49)$$ If I was pressed for an answer I would say this system was unsolvable. If $x \equiv b(100)$ the $x = b + 100t$. Then $b + 100t ...
0
votes
1answer
25 views

Linear equation with residue classes

I'm having a hard time solving an exercise that seems fairly easy: Given a linear map $$ f: (Z/5)^2 \mapsto (Z/5)^2 $$ and $$ f(\bar{2}, \bar{3}) = (\bar{1},\bar{1})$$ $$f(\bar{1}, \bar{4}) = ...
0
votes
1answer
40 views

Why is $U(12) = U_{4} (12) ~ U_3(12)?$

Why is $U(12) = U_{4} (2)~ U_3(12)$ Attempt: Any subgroup $U_k(n) = \{x \in U(n)~~|~~x \mod k=1 , k ~|~n \}$ Hence : if $U(12) =\{1,5,7,11\}$ then : $U_4(12) =\{1,5\}$ and $U_3(12)=\{1,7\}$ We see ...
0
votes
1answer
36 views

Can diagonalization mod p be generalized to diagonalization mod n?

When you diagonalize a matrix $A$, your $D$ matrix will be the similar to if you diagonalized $A$ mod $p$ (but $D$ will also be mod $p$ in this scenario). I'm having a brainfart moment here. Does $p$ ...
0
votes
1answer
82 views

Regarding Gaussian integers and primitive roots.

Can modular arithmetic be set up using gaussian integers instead of (non-complex) integers? If so is there an analogue of 'primitive roots' with Gaussian integers?
0
votes
1answer
28 views

Find one sum in the function of another sum only

Let $S = s_1 + s_2 + ... + s_n$, with $s_i \in N$. Let $M =(p_1*s_1 + p_2*s_2 + ... + p_n*s_n) \bmod{p_{n+1}}$, where $p_i$ indicates $i$-th prime. Find $M$ in the function of $S$ only. Source: ...