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
2answers
148 views

Discrete log modulo prime

I'm trying to understand properties of the discrete logarithm problem modulo a prime. For a prime $p$, an $\alpha \in \mathbb{Z}_p^*$ and $a \in \mathbb{Z}_{p-1}$ why does $\alpha^x \equiv 1 \mod p$ ...
1
vote
0answers
171 views

solving congruence equation system modulo prime

I need to solve a congruence system like this: $30f_0+26f_1+8f_2+38f_3+2f_4+40f_5+20f_6 \equiv 0 \pmod{41}$ $38f_0+2f_1+40f_2+20f_3+30f_4+26f_5+8f_6 \equiv 0 \pmod{41}$ ...
1
vote
4answers
75 views

Find the smallest integer $n\geq1$ such that $35n$ is a perfect square and $n/7$ is a pefect cube.

Find the smallest integer $n\geq1$ such that $35n$ is a perfect square and $n/7$ is a pefect cube. What I have so far: we express the prime factorizations of $35$ and $7$ as $5\cdot7$ and $7$, ...
2
votes
0answers
55 views

System of equations - modular arithmetic

I am asked to solve the following..... Let $n\in \mathbb{N}$ and suppose that $a,b,c,d,k,l\in\mathbb{Z}$. Consider the system $ax + by \equiv k$ mod $n$ and $cx+dy \equiv l$ mod $n$. Let $D=ad-bc$. ...
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 ...
4
votes
2answers
967 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
56 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
27 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
116 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
78 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
36 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
114 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
49 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
68 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
83 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
266 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
97 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
118 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
66 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
52 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
72 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
67 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
72 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
402 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
179 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
79 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
252 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
128 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
32 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
106 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
114 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
85 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
232 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
78 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
57 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
73 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
553 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
190 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
65 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
130 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
40 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
72 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 ...
2
votes
3answers
91 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
88 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
127 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
300 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
30 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}) = ...