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
3answers
121 views

what is the remainder if we divide $72^{200}$ by $5$?

What is the remainder if we divide $72^{200}$ by $5$? I am very new to modular arithmetic! Please help!
0
votes
2answers
52 views

Reducing exponents mod n

Say I have 5^(52) mod 22 How do I reduce this? I know if 22 was a prime number, then I could simply I could simply reduce 5^(22) * 5^(22) * 5^(8) which would become 5^(8) mod 22 but that doesn't ...
2
votes
1answer
97 views

Combining results with Chinese Remainder Theorem?

$9x^2 + 27x + 27 \equiv 0 \pmod{21}$ What is the "correct" way to solve this using the Chinese Remainder Theorem? How do I correctly solve this modulo $3$ and modulo $7$ without brute force?
0
votes
2answers
59 views

Do we not have to follow Euclidean division strictly when doing modulo operations?

Referring to this earlier question of mine, and in particular, the answer of Yiyuan Lee, we have that $(p-1)\equiv -1 \pmod p$, since we have that $(p - 1) : p = 1$ with a remainder of $-1$. However, ...
0
votes
1answer
126 views

Convert modulo 65 into modulo 26.

Is there anyway to convert x ≡ 9 (mod 65) into x ≡ something (mod 26)? Generally is there a way to convet one modulo into some other modulo?
0
votes
1answer
34 views

Proving that $mx \equiv 0 \pmod n$ has $\gcd(m, n)$ solutions in the interval $[0, n-1]$

I wish to prove, using my own intuition, that there are $\gcd(m, n)$ group homomorphisms from $\mathbb{Z}_m$ to $\mathbb{Z}_n$. I have reduced(?!) the problem to proving that there are $\gcd(m, n)$ ...
2
votes
1answer
27 views

How do I calculate the number of times angle X should be added to obtain angle Y?

Suppose I have a angle X=100 and angle Y=60. when we add X 15 times it gives ...
2
votes
3answers
123 views

Modular Arithmetic - Quadratic Solutions Problem

I've just been given the following question in my crypto class, and I think I'm fairly sorted for it, but I was just wondering whether there might be any extra solutions to the ones I've worked out. ...
1
vote
4answers
163 views

Finding remainder when $32^{32^{32}}$ is divided by $7$

I recently learnt modular arithmetic for finding remainders when huge numbers are to be divided by some number. However, I am stuck at this problem: What is the remainder when ...
1
vote
2answers
47 views

Modular Arithmetic - Finding the smallest possible length of the room in inches

I need to know if I've done this proof correctly. Question: A rectangular room is to be tiled with square tiles. Consider only the length of the room. The tiles are available in 9-inch, 10-inch, or ...
0
votes
1answer
62 views

A question on GCD

Let $n_2>n_1>r>1$ be positive integers, let $r\neq gcd(n_i,r)=t>1$ for $i=1,2$ and let $n_1\nmid n_2$. How do you disprove $gcd(n_1,n_2) \bmod r=gcd(n_1\bmod r,n_2\bmod r)\bmod r$? Does ...
1
vote
1answer
432 views

Modular exponentiation with Chinese Remainder Theorem

I'm learning modular exponentiation with Chinese remainder theorem. I found a great answer from below ...
2
votes
2answers
113 views

Clarify a problem with prime and composite numbers

What is the largest positive integer that is not the sum of a positive integral multiple of 42 and a positive composite integer? The solution listed says The requested number $\mod {42}$ ...
1
vote
1answer
28 views

Finding the remainder of a linear congruence

Okay so say I have $314^{420} \equiv r \pmod{1001}$ and I have to find what the remainder is, $r$ in this case. I know you could compute it by $gcd(314^{420}, 1001)$ and using EEA. But the numbers are ...
0
votes
2answers
31 views

Combining divisibility with congruences

If we assume that $x^2 - xy + y^2 \equiv 0 \pmod n$ Then $x^2 + y^2 \equiv xy \pmod n$ If $(x,y,n)=1$. Then we can observe that neither x nor y can divide the ...
1
vote
3answers
54 views

Multiplying modulo 20

For a positive integer $n \ge 2$, define $U(n)= \{k \in \Bbb Z_n $| gcd$(k,n)=1\}$. Then $U(n)$ is a group under multiplication modulo $n$. Find the order of $U(20)$. Is it possible to generate ...
2
votes
6answers
195 views

$9999\ldots 9 \cdot 9999\ldots 9$ will always end with $1$?

Will a number consisting of only the digit $9$, multiplied with another number consisting of only the digit $9$, always result in a number that ends with $1$, and how can one know that this will ...
1
vote
1answer
55 views

GF(113) arithmetic using tables?

I need to work with the Galois Field of (prime) characteristic 113. I am wondering if it is possible to implement multiplication and division using log/antilog tables (like I already do in different ...
1
vote
1answer
46 views

modulo division of inverse numbers

I am working on some modulo arithmetic and I do not seem to understand why $28^{-1} (mod59)= 19 (mod59)=55$ is and not $28^{-1} (mod59) = 0.0035 (mod59)$ ? When I try to calculate this in Java it ...
-1
votes
3answers
131 views

Find the least positive integer with remainders 1,2, and 3 when divided by 7,8, and 9 respectively.

a. Find the least positive integer with remainders 1,2, and 3 when divided by 7,8, and 9 respectively. The three congruences are $ x \equiv 1 $ (mod 7) $ x \equiv 2 $ (mod 8) $ x \equiv 3 $ (mod 9) ...
0
votes
1answer
183 views

Modular Arithmetic - Pirate Problem

I was reading an example from my book, and I need further clarification because I don't understand some things. I'm just going to include the $f_1$ part in full detail because $f_2$ and $f_3$ are ...
1
vote
1answer
58 views

Applying the Chinese remainder theorem

I am trying to apply the Chinese remainder theorem to obtain the unique solution modulo $10^n$ for $N\equiv 1 \pmod {2^n}$ and $N\equiv 0 \pmod {5^n}$. I have reason to suppose that the solution is ...
4
votes
1answer
144 views

remainder of the division of $7^{1203}$ by $143$

I have to find the remainder of the division of $7^{1203}$ by $143$. I thought that I could use the Euler Theorem: Let $a \in \mathbb{Z}$ and $n \in \mathbb{N}$.We also know that $(a,n)=1$.Then ...
1
vote
0answers
63 views

Primality of $P_{q,j}=(2^{q^{j+1}}-1)/(2^{q^j}-1)$ , when $q$ is prime, $j\ge0$?

Let $P_{q,j}=(2^{q^{j+1}}-1)/(2^{q^j}-1)$ , $q$ prime and $j\ge0$. $P_{2,j}$ is a Fermat number, $P_{q,0}$ is a Mersenne number. Apart from Fermat primes and Mersenne primes, and apart from ...
3
votes
5answers
347 views

Modular Arithmetic - Are we allowed to distribute the Modularity?

Assume I have a problem such as "Prove that $\displaystyle103^{53} + 53^{103}$ is divisible by $39$." This would mean I wanted to prove that $\displaystyle103^{53} + 53^{103}\equiv0\pmod{39}$. My ...
2
votes
3answers
56 views

Why do put at $k$ only values from $0$ to $6$

Find an integer $x$ whose remainder of the division with $10$ is $3$ and the remainder of the division with $7$ is $4$. $$x-3=10k \text{ and } x-4=7l$$ From the first equation we get: $ x=10k+3$. ...
8
votes
6answers
422 views

Fermat's Little Theorem: exponents powers of p

I was working with congruence classes and encountered Fermat's little theorem: $$a^{p } \equiv a \mod p$$ But I noticed that a$^{p^{k}} \equiv a \mod p$. I used induction on $k$ but I'm still not ...
1
vote
0answers
109 views

Why doesn't this base 10 number x mod 2^y work for converting base 10 to binary

Okay I tried to convert 1 million to binary by dividing by a power of 2 and taking the remainder and dividing that by a power of 2 and so on and I got this: 1111010000100100000 Google says 1 million ...
2
votes
1answer
74 views

Abstract Algebra Computation

Compute: $3^{47}$ mod $23$ $3^{49}$ mod $7$ $2^{2^{17}}$ mod $23\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ hint: compute first $2^{17} + 1$ mod $19$ This is the first time I've had to ...
2
votes
2answers
68 views

Is the fact that if $x \equiv a\:mod\:b$ then $x^n \equiv a^n\:mod\:b$ also true in reverse?

I'm trying to solve the following question: Show that If $x^2 \equiv x\:mod\:p^k$, then $x \equiv (0\:or\:1)\:mod\:p^k$ where $p$ is prime and $k$ is a positive integer. I've managed to get as far ...
0
votes
1answer
74 views

How is 4 a quadratic residue of 7?

On Wolfram's dictionary, it shows that the quadratic residues of 7 are 1,2,4. It shows that the quadratic residues of 5 are 1,4. I tested 1 and 4, and as you can see: $$1^2 = 1 \pmod 5$$ and $$ 4^2= ...
0
votes
2answers
41 views

Prove that this equation have an non finite number of prime solutions

So the question seeks to answer the following, let $x,y\in\Bbb R$. Prove that there is a non finite number of prime solutions to the following equation: $3x-5y=11$. Our professor says that it's easy ...
0
votes
1answer
50 views

$x_i=x_{i-1}^2+a\pmod{N}$ with $N$ a composite number.

$x_i=x_{i-1}^2+a\pmod{N}$, $N$ is an odd composite number, assume $N=p \cdot q$ with $p,q$ primes, $x_0=1$ then calculate $\gcd(x_i,N)$, for what $a$ the quadratic iterative function give one factor ...
0
votes
2answers
49 views

Primes and Inverses of an integer

I have the following question which I do not understand. Here it is: Consider the primes $5$, $7$ and $11$ as n. For each integer from $1$ through $n - 1$, calculate its inverse. I do not ...
2
votes
2answers
499 views

Hint for finding the remainder when $2018^{2019}$ is divided by 13

I have been thinking of how to answer this. The question is find the remainder of: $$\frac {(2014^{2015}) \space (2016^{2017}) + 2018^{2019} \space}{13}$$ This is what I was thinking: Since $ 13 ...
0
votes
3answers
42 views

Solving linear modular equations

How does $17r \equiv-2 \pmod {11} $ reduce to $r\equiv-4 \pmod {11}$? I know that $-2\equiv9 \pmod {11}$, but how do I simplify the $17$?
0
votes
2answers
48 views

Modular arithmatic, basic question [closed]

How does this: $2x + 3 \equiv -1 \pmod {10}$ directly lead to this: $2x = 6 \pmod{10}$
0
votes
1answer
63 views

Proof that $x^n \mod b = (x \mod b)^n$

I've been messing around with modular arithmetic recently, and stumbled across this, but couldn't find a proof for it anywhere. I hate taking things as truth without knowing why, so could anyone ...
4
votes
0answers
136 views

Solving $x^e\equiv a\pmod n$

I am trying to put together the techniques involved in solving $$x^e\equiv a\pmod n, \text{ for known } n\in\mathbb N^*, e\in\mathbb N^*, a\in\mathbb Z_n, \text{ unknown }x\in\mathbb Z_n$$ I'm ...
0
votes
1answer
145 views

$a ≡ b $(mod $n_1$) and $a ≡ b$ (mod $n_2$), then $a ≡ b$ (mod $n$)

Verify that if $a ≡ b$ (mod $n_1$) and $a ≡ b$ (mod $n_2$), then $a ≡ b$ (mod $n$), where the integer $n = lcm(n_1 , n_2)$. Hence, whenever $n_1$ and $n_2$ are relatively prime, $a ≡ b$ (mod ...
45
votes
5answers
4k views

Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
3
votes
3answers
35 views

Sum of powers of $2$ modulo $11$: $\sum_{i=0}^{5 \cdot x -1} [2^{4i}] \equiv 0 \mod 11$

I tried the proof by reducing the exponents modulo 10, but didn't really get a solution :/. Would love some help :D, thanks guys
3
votes
1answer
53 views

Modular arithmetic - Suggestions to begin

I've always wanted to start studying modular arithmetic to try to solve problems like: $$\text{find } n \in \mathbb{N} : 4n^2 \equiv 1 ~(\text{mod }{10^4})$$ I have a good basis in mathematical ...
0
votes
1answer
88 views

Integers $p,q$ such that $pq\equiv 1 \mod (p+q) $

I want to find pair of integers $p,q$ of the form: $$pq\equiv 1 \mod (p+q) $$ What have I tried so far is: Since, $pq \equiv 1 \implies p$ has inverse element with respect to $p+q$. which means ...
-1
votes
5answers
80 views

If $x \equiv 1 \pmod 3$ and $x \equiv 0 \pmod 2$, what is $x \pmod 6$? [closed]

If you know what a number mod two different primes is (3 and 2) in this case, how can you tell what the mod is of the two products?
1
vote
0answers
72 views

If $x=1\mod3$ and $x=0\mod2$, what is it $\mod6$? [duplicate]

If you know what a number mod two different primes is (3 and 2) in this case, how can you tell what the mod is of the two products?
0
votes
1answer
95 views

Show that the mod p map is a ring homomorphism

Let p be a prime and let (mod $p$)$ : Z[x] \mapsto Z_p[x]$ be the mod-p map which sends any polynomial... $f(x) = a_0 + a_1x + a_2x^2 + · · · + a_nx^n \in Z[x]$ ... to the polynomial... $f(x)$(mod ...
1
vote
1answer
53 views

$a$ modulo ${\prod_{i}p_i}$ where $p_i$ are primes.

This may be a very simple question for many of you. But somehow I can not see how to find a good way to answer this. The question is that if it is given that $$a\equiv k_i\mod{p_i},\quad ...
1
vote
2answers
48 views

Modular arithmetic question related to the fundamental theorem

Somewhat of an unusual homework problem that my professor assigned that I can't wrap my head around. We are only considering the positive numbers congruent to 1(mod 4), that is, other numbers do not ...
0
votes
2answers
32 views

Modular arithmetics

I am having a question specific for this video on Youtube: https://www.youtube.com/watch?v=3QnD2c4Xovk They seem to explain that shared encryption concept pretty well, but I seem to get some incorrect ...