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

2
votes
1answer
22 views

How would you solve this modular equation without being able to find the multiplicative inverse?

If I have $15a \equiv 60 \space mod \space 95$, how could I solve for $a$? The equation has multiple solutions (23 and 42 among them) -- how do I find them without resorting to guess-and-check?
0
votes
2answers
27 views

Relationship between fibonacci number and modulo. [on hold]

Determine with reason whether or not $$F_{5n}=0\pmod5$$ I don't have any idea about it.
1
vote
2answers
20 views

reducing exponent in modular arithmetic

Im struggling with an example excercise because I have problemes to comprehend an step in the calculation $3^{36} \mod 59 = 3^{7} \mod 59$ How can I reduce the exponent $36$ to $7$? I tried it with ...
0
votes
2answers
35 views

Finding the remainder of a division

$75$ is the remainder of $X$ divided by $132$. What is the remainder of $X$ divided by $12$? I know the answer is $3$ but how do we get that answer?
4
votes
2answers
90 views

Nice Question in Mathmatics about Times

I ran into a nice question from one book in Discrete Mathematics. I want to someone lean me how solve such a problem, because I prepare for entrance exam. if the time is "Wednesday 4 ...
0
votes
3answers
28 views

Subgroup generated by and element

Consider the group G = {1, 3, 5, 7} under multiplication modulo 8. What is the order of the element 5? I know that the order of an element is the order of the subgroup generated by the element. so ...
3
votes
2answers
41 views

Proving divisibility by 7 using modular arithmetic [duplicate]

Prove that $2222^{5555} + 5555^{2222}=0 \pmod{7}$. I'm not getting how to start away with this problem. I know that modular arithmetic should be used. Please give me some hints on how to solve this ...
1
vote
2answers
38 views

An expression is divible by 4 but not 8.

Let $n\in\mathbb{N}$. Show that $4\mid(3^{2n+1} + 5^{2n})$ and $8\nmid(3^{2n+1} + 5^{2n})$ $(2m+1)^n = (2m+1)_1(2m+1)_2...(2m+1)_n$. Here I'm trying to show that an odd number raised to any integer ...
-2
votes
1answer
32 views

Question on the relationship of a quantity and its value modulo n [closed]

Is it correct to say that if there are 13 chameleons, then there are $1\pmod 3$ chameleons? If so, why?
0
votes
1answer
37 views

Fast modular exponentiation

Suppose that $p$ and $q$ are distinct primes, then for every integer $a$ and exponent $e$ with $e\not \equiv (\bmod \,(p - 1)(q - 1))$ show that: ${a^e} \equiv {a^{e\, \cdot \,\bmod \,(p - 1)(q - ...
0
votes
3answers
38 views

Modular arithmetic

Hello, What is the remainder when the following sum is divided by 4? $1^5 + 2^5 + 3^5 +...+ 99^5 + 100^5$ I feel like it has to do with modular arithmetic... I am trying to decompose every number ...
3
votes
2answers
29 views

What does the modulo of a non-integer mean?

For example, in the equation $ x=\frac{3}{5} \bmod 11$ The value of $x$ is $5$ according to wolfram alpha. I know how to manipulate the equation to to get the value but I dont understand what the ...
-1
votes
0answers
8 views

How can I solve a mod system of equations for this hill cipher? [duplicate]

I am having trouble eliminating these variables when I try to solve this system of equations. They may not even be the right equations, but it would be nice to see this worked out so I can try my next ...
3
votes
3answers
53 views

Prove the following fraction is irreducible

Prove $\frac{21n + 4}{14n + 3}$ is irreducible for every natural number $n$. I was thinking of taking a number-theory based approach. Can you suggest the following method Calculus/Number theory ...
0
votes
1answer
44 views

Proof that $ax \equiv 1 \mod{n}$ has no solutions when $a$ and $n$ aren't co-prime?

Does this proof work? Is there a simpler one (precluding citing other theorems)? Suppose $ax \equiv 1 \bmod{n}$. Then $ax = kn + 1$. We have some $d = \gcd(a, n)$ such that $a = da'$, $n = dn'$, and ...
0
votes
0answers
31 views

Solving system of equations using mod math for a Hill cipher

I am having trouble eliminating these variables when I try to solve this system of equations. They may not even be the right equations, but it would be nice to see this worked out so I can try my next ...
0
votes
2answers
54 views

Find integers x and y with 103x + 113y=1

Find integers $x$ and $y$ with $103x + 113y=1$ How would you solve this problem? I'm thinking maybe you can use Euclidean Algorithm to solve for the inverse?
2
votes
1answer
85 views

The number $2^{29}$ has $9$ distinct digits. Find the missing digit without the use of a calculator. [duplicate]

$2^{29}$ has $9$ distinct digits. Find the missing digit without the use of a calculator. I've seen its solution before but I still don't understand it. Math novice here. A detailed answer will ...
1
vote
2answers
28 views

Proof of Little Fermat's Theorem for a=7

In the book I read there are proofs of FLT for certain cases before the common case. When a=7, authors first write that it's possible to check all remainders of $a\mod7$, and then that it's ...
1
vote
0answers
52 views

[ANSWERED]Is $\{n, n^{2} n^{3}\}$ a group under multiplication modulo $m = n + n^{2} + n^{3}$?

My number theory has been lacking, so i decided to practice it a bit. I have gotten better in the sense that i can figure out where to begin approaching a problem, but i am having trouble seeing the ...
1
vote
3answers
55 views

Simplifying a proof by contradiction: if $a\equiv 1\bmod 5$, then $a^2\equiv 1\bmod5$

Prove the following either by Direct Proof or by Contraposition: Suppose $a\in\mathbb{Z}$, if $a\equiv 1\pmod 5$, then $a^2\equiv 1\pmod5$ Suppose $a\equiv 1\pmod 5$ Then $5|\left(a-1\right)$, ...
0
votes
1answer
25 views

Explanation of congruence and modulo

Consider the set $A$ = {${-6, -5 -4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12}$} Write down the numbers in $A$ congruent to $1$ modulo $4$. Can someone explain why the answer is not $-4,-1,-4,8,12$ ...
2
votes
1answer
31 views

The modular n-th root (mod p*q)

I am interested in the solution of the following modular equation. Is the solution unique? If not, how difficult do find more than one solutions? $$x^n \equiv a \; \bmod (p\cdot q)$$ where $p$ and ...
1
vote
1answer
30 views

Why is any number to the 1,5,9,13, etc. modulus 10 itself?

Why is $n^{4k+1} \% 10 = n$ for any integer $n$ and any whole number $k$? What about base 10 math makes this sop?
1
vote
0answers
10 views

If there is a subset with sum divisible by n, then take out an integer of the subset. How many moves?

Fix an integer $n \ge 2$. A finite set $A \subset \mathbb{N} $ is given. Define $ s(X) = \sum_X x $, where $ X $ is a finite set. We know that $n \mid s(A)$. We can do just one move: if there is a ...
0
votes
1answer
18 views

(Statistics)Probability of given sum in dice tossing [closed]

I need some help with this problem: By tossing two dice, what is the probability of: i) Total sum of 7 ii) Difference of 5 iii) Total sum multiple of 7 Thanks everyone ~Chris
0
votes
3answers
44 views

Congruences in number theory

I am working on a worksheet on number theory and I have to solve the following congruences: $$7^{128}=n\mod 13$$ Find $n$. And $$28x^2=1\mod37$$ How should I solve these congruences? I have no clue ...
1
vote
2answers
61 views

Find the remainder when $2^{561}$ is divided by $561$ using simple congruence properties.

$2^{561}\equiv ? \pmod{561}$ Few observations : $561 = 3\times 11\times 17$ So Fermat's little theorem is not useful here. Any hints ? If possible, kindly avoid carmichael numbers/group theory/euler ...
0
votes
0answers
21 views

Modular nth roots, e.g. $x^5 \equiv 6 \pmod{31}$

I want to algorithmically solve the (large integer) modular root equation $$x^n \equiv a \pmod {p^k},$$ assuming for simplicity that $p$ is prime, $\gcd(a,p)=1\;$ and $n$ odd. If $q \equiv n^{-1} ...
0
votes
0answers
22 views

CRT Algorithm using InvMod + Undefined

I am trying to implement a modified CRT function in c++ that calls a function called invMod which is simply the inverse modulus function. I am having difficulty randomly generating values while ...
1
vote
1answer
12 views

$A^{-1}x \pmod{26}$ and coprime requirement in Hill cipher

I am reading Hill cipher from wiki page and I have been stuck on this thought for a while. Why is there a requirement for $\det(A)$ and $26$ to be coprime in Hill cipher ? Anybody familiar with Hill ...
0
votes
1answer
44 views

Exist an explicit formula to calculate the minimum number of divisions by two that leave a rest < 0.5?

I have a number $x \in \Bbb R/\Bbb Z$ (i.e. any number but entires) and I want to know if exist a explicit formula that evade recursion to calculate the minimum n that $$\frac{x}{2^n}\mod ...
0
votes
2answers
27 views

Proof of $g^a \equiv 1 \pmod{m}$ and $g^b \equiv 1 \pmod{m} \quad \implies \quad g^{\gcd(a,b)} \equiv 1 \pmod{m}$

I am trying to understand the following: $$g^a \equiv 1 \pmod m \quad \text{and} \quad g^b \equiv 1 \pmod{m} \quad \implies \quad g^{\gcd(a,b)} \equiv 1 \pmod{m}.$$ I have tried a few approaches, ...
1
vote
1answer
45 views

Calculation of products of powers using Modular Exponentiation

I need to devise an algorithm that outputs $x^a * y^b$ (mod $m$) on an input of $m, x, y, a, b$ using the binary left to right modular exponentiation algorithm. It should be able to compute $x^{22} * ...
0
votes
0answers
31 views

How can I solve equations involving modulo both side like this one?

I need to find $x \bmod m$ from the below equation: $$((p \bmod m)(x \bmod m)) \bmod m \equiv q\bmod m$$
0
votes
5answers
53 views

How to work out $-1 \bmod 7$?

What is the working out for $-1 \bmod 7$? I can do it if the numbers are positive just the negative throws me off.
0
votes
1answer
19 views

On the Product of Congruence Classes over $\mathbb{Z}$

Is it possible to multiply an element $a$ of $\mathbb{Z}_4$ to an element $b$ of $\mathbb{Z}_2$? If so, what are the needed conditions? To which set ($\mathbb{Z}_4$ and $\mathbb{Z}_2$) does $a\cdot b$ ...
1
vote
1answer
38 views

How to figure out congruences involving large numbers?

The one I'm stuck on now is: $$3^{1996001} ≡ 2664001 \mod 3992003$$ Absolutely no idea how to get this! I could whittle it down if I knew the multiplicative order of $3$ modulo $3992003$, but I have ...
1
vote
3answers
74 views

Remainder of dividing $x^{137}+x+1$ by $x+5$

In $\mathbb{Z}_7[x]$, what is the remainder of dividing $x^{137}+x+1$ by $x+5$? I can not find how to solve this problem of modular arithmetic. Anybody could tell me only as I proceed to solve this ...
0
votes
0answers
22 views

In $\mathbb{Z}(430)$, What is the value of $x ?. 9 * x = 80 ^{ -1}$

In $\mathbb{Z}(430)$, What is the value of $x ?. 9 * x = 80 ^{ -1}$ I can not solve this problem. I the inverse of a number is calculated in my case is 80 But in this case the number is multiplied ...
4
votes
2answers
130 views

Solving strange Modular arithmetic

I'm trying to solve a form of modular arithmetic I've never seen before. I'm completely stuck. Any hints in how to crack this would be of great help. $$ -18 \equiv 19y \pmod{1967-y}$$ Or ...
2
votes
0answers
28 views

Fast algorithm/formula for serial range of modulo of co-prime numbers [migrated]

In my project, one part of problem is there. But to simplify, here the problem is being formulated. There are two positive co-prime integers: $a$ and $b$, where $a < b$. Multiples of $a$ from 1 ...
2
votes
1answer
54 views

How can I compute the following fast?

What approach should I adopt for computing the following problem fast? $$f(n) = \sum_{i=1}^n (n \mod i)$$ $$ 1\le n \le 10^{10}$$ Since the answer can be huge I have to output it modulo some given ...
0
votes
0answers
17 views

how to use inverse moldulus operation while taking modulus?

i want to calculate (a/b)mod m which is definitely not equal to (a%m)/(b%m)..... so we can calculate the inverse of b and multiply it to a then take modulus i.e (a%m * x%m)%m where (b*x=1 mod m) and ...
0
votes
1answer
54 views

Closed form of the series

I want to evaluate $\sum_{i=1}^{n} (x+i)^4$ So what i did is, after expanding it i reduce it to following form $ x^{4} * n + 4 x^{3} * \sum_{i=1}^{n}i + 6x^2\sum_{i=1}^{n}i^{2} + ...
0
votes
1answer
54 views

Variation of Fermat's Theorem

I'm am having trouble coming up with a proof strategy for the following variation of Fermat's Theorem. If the solution is trivial, please forgive me, this is my first encounter with this theorem. I ...
1
vote
0answers
32 views

Rational equality modulo $p$

Assume that we have two rational expressions $f,g\in \mathbb{Z}(x,y_1,\ldots,y_n)$ with the property that the variable $x$ can only appear in the numerator of $f$ while only in the denominator of $g$. ...
3
votes
1answer
35 views

Find the order of $2$ in $\mod 2^{n} -1 $

Find the order of $2$ in $\mod 2^n-1$ I know that the order of $2$ in $\mod 2^n-1$ is the smallest positive integer $k$ such that $$2^k \equiv 1 \pmod {2^n-1}$$ How to proceed from here ? Any ...
0
votes
1answer
25 views

$(x \equiv k^2 \mod 3) \iff x \equiv 1 \mod 3 $

Is it true that if 3 does not divide $x$, $$x\equiv k^2\mod 3 \iff x\equiv 1 \mod 3$$ If the above statement is correct , There are two parts to prove $$x\equiv k^2\mod 3 \implies x\not\equiv 0 ...
1
vote
4answers
82 views

Calculate $85^{2014}\bmod {82}$ [closed]

Calculate the following equation $$85^{2014}\equiv x \bmod {82}$$ Answer is 73 in Wolphram Alpha, but I always lose myself doing the step by step