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
0answers
62 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 ...
5
votes
2answers
3k 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
30 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
36 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
29 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
36 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
63 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
26 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
79 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
130 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
65 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
49 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 ...
3
votes
2answers
644 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
84 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
69 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
29 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
85 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
185 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
88 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
49 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
55 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
342 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
130 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
50 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
230 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
121 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
91 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
85 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
55 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
127 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
48 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
377 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
132 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
66 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 . ...