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
1answer
138 views

Generators of $\Gamma(7)$, congruence subgroup of modular group

L.s., I try to do some calculations on the Klein Quarctic curve, but there is a basic thing I don't know how to compute. Let $\Gamma(7)$ denote the congruence subgroup of the modular group PSL(2, ...
0
votes
1answer
19 views

Modular Group Arithmetic with Primes

I need help understanding what this means: Working in sets $\mathbf Z_N^* = \{a \in \{0,1,...,N-1\} : gcd(a,N) = 1\}$ If I have a prime $p$ then I claim there is a value $k$ such that $g^x = ...
2
votes
2answers
49 views

$2^n$ modulo n where n is odd always yields either an even or $1$

I'm attempting to do a pidgeonhole proof to prove that for some odd integer n, there is always a $2^k$ such that $2^k \mod(n) = 1$. I know that $2^n \mod(n)$ will always yield either an even number or ...
0
votes
1answer
74 views

The relationship between the mod value of 2 numbers?

I've been trying to study on my own, the relationship between 2 numbers as you move down the number line from a starting point and could use some help. I believe this could be described as modular ...
1
vote
0answers
60 views

Group of invertible elements, isomorphic to $Z_4$?

The group $f(8)$ of invertible elements in the ring $Z_{10}$ has four elements, $f(10) = \{ [1,], [3], [7], [9]\}$. Is this group isomorphic to $Z_4$ or to the symmetry group of the rectangle? ...
1
vote
0answers
45 views

Finding modular variable from some information about multiplications

I have got a very specific mathematic/algorithmic problem. In fact, it is a an automata theory problem(buchi automaton), but this problem seems to be naturaly translated into a modular arithmetic ...
2
votes
3answers
55 views

modular arithmetic proof

Suppose $x$, $y$, and $z$ are integers and $x= 3y^2 -z^2$. Prove that $x\not\equiv1\mod4$. My thoughts: So I am not sure the route that can prove this. I am trying to just use the simple stuff to ...
0
votes
1answer
60 views

finding a unique integer using mod

Consider two different prime numbers $x$ and $y$. Show that the following is true: For every pair of numbers $m$ and $n$ so that $0\le m<x$ and $0\le n< y$, there is a unique integer $q$, where ...
3
votes
2answers
615 views

Find the last two digits of $3^{45}$

I was wondering if there is a simpler way to find the last to digits of a power such as $3^{45}$. I reduced it modulo 100 to get the answer, which is 43. But I was curious if there was a simpler, or ...
0
votes
0answers
56 views

Chinese Number Theorem w/ extended Euclidean Algorithm

I am given the following: 153 = x^3 mod 155 196 = x^3 mod 203 27 = x^3 mod 117 My first thought was that I could turn this into an equivalence and say ...
1
vote
3answers
119 views

Prove that, given integers a, b, and c such that a mod 6 = 3, b mod 8 = 3, and c mod 10 = 3, (a + b + c) mod 6 is odd.

I need to prove that, given integers $a$, $b$, and $c$ such that $a\mod6=3$, $b\mod8=3$, and $c\mod10=3$ then, $(a + b + c) \mod6$ is odd. Here's what I have tried. By using the definition of mod ...
2
votes
2answers
64 views

Show that $17$ divides $6^{3n+2} - 2\cdot 29^n$ for all natural numbers $n$

Show that $17$ divides $6^{3n+2} - 2\cdot 29^n$ for all natural numbers $n$. I know that if $$17 \mid 6^{3n+2} - 2\cdot 29^n$$ then $6^{3n+2}$ is congruent to $2\cdot 29^n$ mod $17$. But how ...
0
votes
2answers
65 views

If $a \equiv b\mod n$ then what is $a^m \mod n$ in terms of $a,b,n,m$?

If $a \equiv b\mod n$ then $a^m \equiv x \mod n$. Please express $x$ in terms of $a,b,n,m$. Also please provide an explanation, if possible.
1
vote
2answers
124 views

determining order of $x+1$ given the $x$ has order three

I was trying to expand $(x+1)^n$, then plug $x^3$ in to the expansion of the $(x+1)^n$, keep trying it until I get the order, are there any other ways? So if $x^3\equiv 1\pmod y$, how would I ...
2
votes
4answers
123 views

Don't know how to continue modulo reduction

Ok , so the question is to find the last three digits of $2013^{2012}$. After some reduction using Euler's Theorem I got $13^{12}$(mod 1000). I tried dividing it in 8 and 125 and later use the CRT , ...
1
vote
3answers
102 views

Find all $n\in\mathbb N$, $n>3$ such that $p(n)=2n+16$, where $p(n)$ is the product of all the prime numbers less than $n$.

Find all $n\in\mathbb N$, $n>3$ such that $p(n)=2n+16$, where $p(n)$ is the product of all the prime numbers less than $n$. E.g. $p(7)=2\cdot3\cdot5$ (and $n=7$ is a solution). Let ...
1
vote
3answers
103 views

Divisibility test for $4$

Claim: A number is divisible by $4$ if and only if the number formed by the last two digits is divisible by $4$. Here's where I've gotten so far. Let $x$ be an $(n+1)$-digit number. So $x= ...
0
votes
3answers
210 views

Incongruent solutions to $7x \equiv 3$ (mod $15$)

I'm supposed to find all the incongruent solutions to the congruency $7x \equiv 3$ (mod $15$) \begin{align*} 7x &\equiv 3 \mod{15} \\ 7x - 3 &= 15k \hspace{1in} (k \in \mathbb{Z}) \\ 7x ...
1
vote
1answer
68 views

$17$ is a quadratic residue for all primes $p$ such that $p \equiv \pm 3 \mod{8}$?

Trying to prove that $17$ is a quadratic residue for all primes $p$ such that $p \equiv \pm 3 \mod{8}$? Thanks!
0
votes
1answer
50 views

Is it true (based on Euler's theorem)

I saw somewhere that by using Euler's Theorem for m=77 we have: "$27^{60}\ \mathrm{mod}\ 77 = 1$ and by using modular exponentiation we also have : $27^{10}\ \mathrm{mod}\ 77 = 1$" For example : if ...
1
vote
0answers
46 views

Identity based encryption

I am implementing ID based encryption in c# right now i am having problem at the following mathematics $$H_1: \{0,1 \}^n \times \{0,1 \}^n \to \mathbb{Z}^*_p, \text{ what does this expression ...
1
vote
1answer
90 views

$\mathbb Z_n$ modular tables , invertible elements and zero/nonzero divisors

Based on $\mathbb Z_n$, with $n\leq10$, make a guess about which elements in $\mathbb Z_n$ are invertible and which are nonzero divisors. Does your guess imply that every nonzero element is either ...
1
vote
1answer
68 views

Solving $x^5 \equiv 7 \mod 13$

I was taking a look at previous exam papers for my course, and found this question: solve $x^5 \equiv 7 \mod 13$ The solution goes as follows, suppose $\overline{x}^5 = \overline{7}$, then for any ...
2
votes
2answers
119 views

Prove that $ax=0$ has a nonzero solution in $\mathbb{Z}_n$ $\Leftrightarrow$ $ax=1$ has no solution.

Let $a\neq 0$ in $\mathbb{Z}_n$. Prove that $ax=0$ has a nonzero solution in $\mathbb{Z}_n$ if and only if $ax=1$ has no solution. $\textbf{My proof (just one way)}$: ($\Rightarrow$) Suppose $a\neq ...
0
votes
1answer
32 views

Finding Solutions of Equations in $\mathbb{Z}_5$

This one should be easy. Just want to make sure I'm doing the right thing. Find the solution of the following equations in $\mathbb{Z}_5$: a) $x + 4 = 0$ b) $3x = 1$
3
votes
1answer
68 views

Deduce the value of a number by only apply modulo operation

For an unknown 16 bit number U, an N (8 bit) modulo operation can applied, which results in a known 8 bit number ...
0
votes
3answers
65 views

How many subgroups there is for $\mathbb{Z}_{23}\times \mathbb{Z}_{31}$?

How many subgroups there is for $\mathbb{Z}_{23}\times \mathbb{Z}_{31}$? I try to understand how to solve it but I don't finding a way... I'll be glad if you help me with this... Thank you!
0
votes
1answer
165 views

Finding the decoding formula and decoding message

Find the decoding formula for the encoding formula $y=9x+10$ and use it to decode "KOMF" Please give me a clear explanation and step by step solutions. Thank you.
0
votes
3answers
40 views

Invertible or zero divisor in $\mathbb Z_n$

Is it true (for $n \le 10$) that every nonzero element in $\mathbb Z_n$ is either invertible or a zero divisor? Can anyone please help me. Thank you
1
vote
3answers
56 views

Trying to remove a mod from an equation.

$376$ is a number that for positive integers $n$, $376^n$ will always end with the number $376$. Now knowing that $376^k \mod 1000 = 376$. How do you prove that the following is true. $$ 376^k \mod ...
1
vote
2answers
120 views

Solving quadratic modulo congruence: review.

I've been trying to solve a quadratic modulo congruence and I think I have the right solution, but in the end there's two things: 1) I cannot explain how $\sqrt(12)$ divided by 2 mod 23 is equal to ...
0
votes
2answers
73 views

For which values of $m$ $x^3\equiv 100 \pmod m$ is solvable?

While trying to get around this question, which is the positive integers solutions to $x^3=y^5+100$, I did some simple manipulations to get: $$q|y\implies x^3\equiv100\pmod q\\ p|x \implies ...
0
votes
2answers
46 views

Congruences help

Theorem: Let m be a positive integer. If a ≡ b (mod m) and c ≡ d (mod m), then a + c ≡ b + d (mod m) and ac ≡ bd (mod m). Proof:We use a direct proof. Because a ≡ b (mod m) and c ≡ d (mod m), by ...
1
vote
1answer
50 views

$p \equiv 5 \mod8\Rightarrow p=(2x+y)^{2}+4y^{2}$

If $p \equiv 5 \mod8$ , then $p=(2x+y)^{2}+4y^{2}$,for some x and y integers. Thanks Here is my approach: I know $p \equiv 5 \mod8\Rightarrow $ $p \equiv 1 \mod4\Rightarrow $ $n^{2}+m^{2}=p\equiv ...
2
votes
1answer
57 views

Show that for all natural $a$, $2008\mid a^{251}-a$.

How to show, that for all natural $a$ coprime to 2008 the following occurs: $2008\mid a^{251}-a$? This means, that $a_{251} \equiv_{{}\bmod 2008} a$, right? It's obvious if $a\mid 2008$. In the ...
1
vote
2answers
58 views

modular exponentiation where exponent is 1 (mod m)

Suppose I know that $ax + by \equiv 1 \pmod{m}$, why would then, for any $0<s<m$ it would hold that $s^{ax} s^{by} \equiv s^{ax+by} \equiv s \pmod{m}$? I do not understand the last step here. ...
0
votes
1answer
45 views

Modular arithmetic to find the mod of a large number

If $x \equiv 23 \bmod 317$ and $x \equiv 25 \bmod 331$, what is $x \bmod 104927$? What techniques are typically used to solve problems of this nature? It doesn't seem clear to me that it can be solved ...
2
votes
2answers
163 views

Determine the smallest multiple of 9 which divided by each of the numbers 2, 5 and 11 leaves a remainder 1.

The question is: Determine the smallest multiple of 9 which divided by each of the numbers 2, 5 and 11 leaves a remainder 1. The answer is 441. What I did when I tried solving this was to set up 3 ...
4
votes
2answers
74 views

Can the decimal digits of $5^a + 7^b$ end in $82$?

I had a question in my exam: Let a and b be a pair of positive integers. In computing $5^a + 7^b$, one gets a number with two least significant decimal digits equal to $82$. Is it possible? ...
4
votes
1answer
88 views

Carmichael Number

I am little bit confused with the definition of Carmichael Number Wikipedia(http://en.wikipedia.org/wiki/Carmichael_number) saying that Carmichael Number is a composite number satisfies ...
0
votes
4answers
66 views

polynomial time in finding constituent prime factors of an integer

If given an integer n = pq, p and q are primes, and a way of computing phi(n) in polynomial time is given. Can we also get the value of p and q in polynomial time? The answer is we can, but how? We ...
1
vote
2answers
108 views

Quadratic residue of $-1$ in composite modulus

It is true for each odd prime number p that if $x^2\equiv-1 \pmod p$ then $p\equiv1\pmod 4$ I've observed that it should be true for all composite integers, whose prime factors are congruent to $1$ ...
1
vote
1answer
30 views

Proof for exponentiation in modular arithemetic

I have found out, that the following is true for modular arithmetic when $t$ is a natural number. $$a^t \bmod\ n \equiv (a\bmod\ n)^t\bmod\ n$$ But I have been unable to find a proof for this, does ...
1
vote
1answer
79 views

division and remainders

When you divide, it will not always result in whole number. Sometimes there will be numbers left over. You can either end the problem with a remainder or use decimal points to get a decimal number. ...
2
votes
2answers
348 views

Prime number test and Fermat's little theorem

We've learn in class that if $a^{p-1} \not\equiv 1 \pmod p$ then $p$ must be a composite number. What is the explanation for that? Thanks!
1
vote
0answers
51 views

Is the modulo operation a standard mathematical operation which actually means Euclidean division?

I was having this long discussion with a colleague as to whether the Modulo operation is a standard mathematical operation or not. He insisted the programming languages don't have a defined standard ...
0
votes
3answers
158 views

$2017$ as the sum of two squares

Write the prime $2017$ as the sum of two squares $2017$ can be written as the sum of two squares because it is a prime of the form $p\equiv 1\ ($mod $4)$ Using an appropriate algorithm find the two ...
1
vote
4answers
231 views

Find the last two digits of 9^(9^9) [duplicate]

I want to find the last two digits of $9^{9^9}$, that is $9$ raised to the power $9^9$. I tried using Euler's theorem but I can't make anything of it. As always, I ask only for a minor hint, not a ...
0
votes
1answer
53 views

Modulo and Congruence

Little Fermats theorem states that If $n$ is a prime number then $a^n \equiv a \mod{n}$ Equivalently If $n$ is a prime number and $a$ is not divisible by $n$ then $a^{n-1} \equiv 1 \mod{n}$ My ...
0
votes
1answer
48 views

System of linear equations over $\mathbb{Z}_p$

Something like this: $$ \begin{cases} x_1+4x_4=1\\ x_1+2x_2+4x_3=3\\ 2x_1+2x_2+x_4=1\\ x_1+3x_3=2 \end{cases} $$ over $\mathbb{Z}_5$ I'm fine with solving it in regular $\mathbb{Z}$ but have no idea ...