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

What is the remainder when $24^{1202}$ is divided by $1446$?

I tried remainder theorem but that does not simplify it. I tried factorizing $1446$ as $2\cdot3\cdot241$ and got remainders when numerator is divided by $2,3$ and $241$ individually but then I did ...
-1
votes
1answer
28 views

Congruents and modulo question- counterexample

I have tired an couple and none seem to be working
2
votes
1answer
68 views

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$.

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$. This is a problem from a selection to IMO 2014. I like thinking about this problem, it is ...
0
votes
2answers
24 views

Why does $y^{pq} ≡ y $[mod $pq$] imply $y^{pq} ≡ y [$mod $p$] and $y^{pq} ≡ y [$mod $q$]? $p, q$ prime.

Why does $y^{pq} ≡ y $[mod $pq$] imply $y^{pq} ≡ y [$mod $p$] and $y^{pq} ≡ y [$mod $q$]? where $p, q$ prime. I can't see it from re-writing it as $y^{pq} = y + kpq$ for some integer $k$, as you ...
1
vote
2answers
34 views

Solve by using modulo. Or something else

An infinite sequence of positive integers $a_1, a_2,\ldots$ has the properties that for $k\geq2$, the $k^\text{th}$ element is equal to $k$ plus the product of the first $k-1$ elements of the ...
1
vote
2answers
42 views

Property of modulo division

I wanted to check if it is true, that $$a^{3b} \pmod n = (a^{b} \pmod n)^{3}\ ?$$ For example when $a = 2, b = 4, n = 5$ I have that $2^{12} \mod 5 = 1$ and $(2^4 \mod 5)^3 = 1$ Is that always true, ...
0
votes
2answers
38 views

Property of Modular arithmetic

If I know that $$g^a \neq 1 \mod b$$ is that always true that if I will take a positive integer $c$ and count $(g^a)^c$, then $$(g^a)^c \neq 1 \mod b$$?
2
votes
2answers
31 views

Why is $a^{n/2} \equiv -1 \mod p$ but not necessarily -1 modulo a composite?

I'm going over a review sheet in preparation for my number theory final. We are asked to prove the following: |a| = 2r, show that $a^r \equiv -1\mod p$ a prime. Does this hold modulo n, where n is a ...
2
votes
2answers
42 views

Cannot find length of repeating block in decimal expansion for $\frac{17}{78}$

I am trying to find the length of of the repeating block of digits in the decimal expansion of $\frac{17}{78}$. On similar problems, that has not been an issue. Take for instance $\frac{17}{380}$. My ...
1
vote
1answer
15 views

Using information from a congruence to factor a number

I am being asked to factor $15347$ given that $7331^2 \equiv 1460^2 \pmod{15347}$. I've tried playing around with each of the numbers -- prime factorization, gcd, lcm, etc., but I can't find a ...
1
vote
1answer
26 views

finding $m$ from $c = m^e \pmod{n}$

I'm working through an RSA encryption example, and I'm being asked to solve $c = m^e \pmod{n}$ for $m$ given c, e, and n (along with its factorization.). Since I already have that information ...
2
votes
4answers
254 views

Find number x such that $x\equiv 4^{1002}\pmod{55}$

Find a natural number x, for $0 \le x \le 54$ such that is a solution for the following equation: $$x\equiv 4^{1002}\pmod{55}$$ This question was asked in an exam, so I expect that the answer is ...
0
votes
1answer
33 views

Simple modulo congruence operation

Find a number $n$, with $0 \leq n < 15$, so that $6 \times 7$ is congruent to $n$ modulo $15$ Please explain your work.
2
votes
2answers
47 views

Showing equality of primitive roots with quadratic non-residues.

Suppose that $p$ and $q = 2p + 1$ are both odd primes. Show that the $p − 1$ primitive roots of $q$ are precisely the quadratic non-residues of $q$, other than the quadratic non-residue $2p$ of ...
0
votes
0answers
58 views

Matrix Induction proofs using $\rm mod$.

Please could someone advise me on where to even start with this question. Thanks in advance Let $A$ be an $n\times n$ matrix, for some $n\geqslant 1$. Given any prime number $p\gt1$, write $A_p$ for ...
1
vote
4answers
42 views

How to find all elements in Z/80 that have multiplicative inverses.

I need to find all the elements in Z/80 that have multiplicative inverses. Z/80 is not a field, so I know not every element will have an inverse. Is there a shorter way than just writing out the ...
0
votes
0answers
31 views

How to calculate sum of digit of a power

Find the sum of the digits of: $$\left\lfloor\frac{k^{h+1}-1}{h-1}\right\rfloor$$ I need to calculate sum of digits in answer. Note as $k$ and $h$ can be a very big value, answer is getting ...
1
vote
3answers
62 views

Calculating $x^{103} \equiv 2 \pmod{143}$

I need to find x, given that: $0\leq x \leq 143$ and $x^{103}\equiv 2 \pmod{143}$. I tried to use Euler's theorem $p(143)=120$, but it didn't help.
0
votes
0answers
34 views

Sum of the jumbled digits of $abc_{10}$ is $3194$

In the book that I am reading, the author denotes $abc_{10}$ as $100a+10b+c$ where $a, b, c \lt 10$. So if $a = 3$, $b=2$ and $c=8$ then $abc_{10} = 328$. The author asks the following problem: In ...
0
votes
0answers
10 views

Quadratic function as permutation of sequence

Say I have a $n \in \mathbb{N}$ and $$a_i := (1,2,...,2^n)$$ and two function $$f(i) = \sum_1^i i = \frac{i(i+1)}{2}$$ $$g(i) = f(i) mod 2^n$$ When I now look at a new sequence $$b_i = (a_{g(0)}, ...
2
votes
2answers
165 views

What are primitive roots modulo n?

I'm trying to understand what primitive roots are for a given $\bmod\ n$. Wolfram's definition is as follows: A primitive root of a prime $p$ is an integer $g$ such that $g\ (\bmod\ p)$ has ...
0
votes
1answer
16 views

Matrix double modulo multiplication to get identity

I have to multiply to matrices A and B which can consist of numbers 0,2,3,4,5,6 to get an identity matrix, however multiplication happens with moduli after every ...
0
votes
1answer
32 views

How to show $2^{k+2}$ divides $3^{2^k}-1$ but $2^{k+3}$ doesn't?

I've got a task: Find highest power of 2 that divides $3^{2^k}-1$ so i wrote few terms and guessed that it's $2^{k+2}$, now i should show it. I tried by induction, but what i got appeals to me as a ...
0
votes
1answer
23 views

How to prove $N=13\times12v+6\times19u$ is a solution for the system?

Well, I have a system of congruences it is : $$n\equiv13\pmod{19}$$ $$n\equiv6\pmod{12}$$ I'm trying to prove that for any pair of integers $(u,v)$ the number $N=13\times12v+6\times19u$ is a solution ...
1
vote
0answers
27 views

Floor function inequality: $\frac{n^2}{x}-\left\lfloor\frac{n^2}{x}\right\rfloor+\frac{2n+1}{x}-\left\lfloor\frac{2n+1}{x}\right\rfloor<1$

I would like to dissect the following inequality to figure out its properties. $$\frac{n^2}{x}-\left\lfloor\frac{n^2}{x}\right\rfloor+\frac{2n+1}{x}-\left\lfloor\frac{2n+1}{x}\right\rfloor>1$$ ...
3
votes
1answer
59 views

How to show $(n-1)^3n^3(n+1)^3$ is divisible by 7 and 9?

Yeah it looks like a basic, really elementary question, but i'm having hard time with it. First i tried to show that it's divisible by 9 $$(n-1)^3n^3(n+1)^3 = ((n+1)(n-1))^3n^3 = (n^2-1)^3n^3 = ...
0
votes
1answer
24 views

Find all values of parameter A such that two system of congruences are equal

I'm starting to learn some elementary number theory and i came across a task i don't know how to solve. $$x \equiv 5 (mod \ 6)$$ $$x \equiv A (mod \ 35)$$ and the second one $$x \equiv A (mod \ ...
1
vote
2answers
31 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
31 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
53 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
21 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
0answers
7 views

Number of solutions to a congruence in a PID

This is the proof that there are $(a,m)$ solutions to $ax\equiv b \mod m$ for the ring $\mathbb{Z}/m\mathbb{Z}$. Where does this proof not hold for a general PID, allowing for (for instance) an ...
0
votes
2answers
29 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
299 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
54 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
19 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
38 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
53 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
18 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
26 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
44 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
28 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
64 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
63 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
55 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
73 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
32 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
27 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
46 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
4answers
56 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 ...