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
2answers
25 views

How to apply Chinese Reminder Theorem to this congruence system?

\begin{align*} 17x & \equiv -15 \pmod{5}\\ -11x & \equiv 5 \pmod{3}\\ 23x & \equiv 15 \pmod{7} \end{align*} $5$, $3$, $7$ are coprime, so the system has solution mod $105$. I'm not sure ...
0
votes
0answers
34 views

No square has a decimal expansion ending in 79

Show that no square number has a decimal ending in 79. More generally, find all possible two-digit endings for squares. Let any digit number ending at 79 be represented as $$a_nx^n+.....+7x+9$$ Plug ...
11
votes
2answers
374 views

Are integers mod n a unique factorization domain?

I am trying to learn abstract algebra from scratch, jolly stuff, but in the process of doing so this puzzles me: Having a ring of integers mod $n$, where $n=pq$ is composite, as I understand we have ...
5
votes
8answers
86 views

How to show $(3^ {2n} - 1) \equiv 0 \mod 8$

How can I show that $$3^{2n}-1 \equiv 0 \pmod 8$$ is true? What kind of method should I approach this problem with? I was thinking induction but but chapter isn't about induction so need some help......
1
vote
1answer
26 views

Remainder modulo matrices.

Is it possible to have a consistent definition of $A\bmod_{left} B$ that respects matrix multiplication from left where $A$ and $B$ are two square matrices with non-negative entries? Is there a ...
2
votes
0answers
29 views

Proof of the Ribet's theorem

My question is very simple : My goal is to read a proof the proof of the epsilon conjecture proven by Ken Ribet (1986) which is an ingredient of the proof of the Fermat Last Theorem (I want the ...
0
votes
4answers
10k views

Calculator model with mod function?

I'm wondering does anyone know of a scientific calculator with a mod function? In C# this is shown as follows (just in case there are any other mods that a mathematical non-savant such as myself ...
1
vote
0answers
11 views

What are good parameters for an $ax+b \pmod{2^L}$ hash with distinct first n bits of the first $2^n$ inputs?

I'm hashing 64 bit integers via $ax+b \pmod{2^{64}}$. Good parameters mean that, given an $1 \leq n \leq 64$, the first $n$ bits of the first $2^n$ inputs are distinct. How should I chose $a$ and $b$ ...
0
votes
1answer
30 views

Calculating the last digit of exponent

I need to calculate the last digit of $723^n$.(For every positive integer $n$). If it was to calculate the last digit of $a^b$ when I know the value of $a$ and $b$,then it was easy- for example,If I ...
-1
votes
0answers
54 views

A square-related question in modular arithmetic…

Let $n$ and $k<\frac{n}{2}$ be integers with $4|n$. Find the pairs $(n,k)$, such that: $i(k-1)\not\equiv\frac{n}{2}\pmod n$, for all $i\in\mathbb{Z}_n$, or $i(k+1)\not\equiv\frac{n}{2}\pmod n$, ...
0
votes
4answers
84 views

Why k should be odd? [duplicate]

My teacher once said, for any positive number $\ n, $ $\ n^k - 1 $ would always have $\ n-1 $ as a factor for all positive odd values of $\ k $. Could anyone tell me the proof? I have written my ...
2
votes
0answers
49 views

Finding solutions in modulo

If I know $x$ modulo m and n, then under what conditions on m,n and p will i necessarily know $x$ modulo p? My initial guess is only in trivial cases, i.e. p is a multiple of m or n, but i cant seem ...
3
votes
4answers
77 views

Find $6^{1000} \mod 23$ [duplicate]

Find $6^{1000} \mod 23 $ Having just studied Fermat's theorem I've applied $6^{22}\equiv 1 \mod 23 $, but now I am quite clueless on the best way to proceed. This is what I've tried: Raising ...
1
vote
3answers
299 views

Find the remainder $4444^{4444}$ when divided by 9 [duplicate]

Find the remainder $4444^{4444}$ when divided by 9 When a number is divisible by 9 the possible remainder are $0, 1, 2,3, 4,5,6,7,8$ we know that $0$ is not a possible answer. My friend told me the ...
4
votes
5answers
171 views

Find $3^{333} + 7^{777}\pmod{ 50}$

As title say, I need to find remainder of these to numbers. I know that here is plenty of similar questions, but non of these gives me right explanation. I always get stuck at some point (mostly right ...
-1
votes
2answers
36 views

Given $(c -x) % (n - 1) == 0$ for some $x$, how do I find a suitable $x$?

Given $(c - x)$ $mod$ $(n - 1)$ $= 0$ for some $x$, how do I find a suitable $x$? $c$ = constant $x \ge 2$ $n - 1$ = constant
0
votes
4answers
71 views

How to approximate

I was reading a book and saw this approximation $(1 - 10^{-3})^{1023} \approx 2^{-1.476}$ I am wondering how it is calculated.
4
votes
1answer
73 views

Pattern in numbers

I bumped into this mathematical calculation while driving my car. With lot of traffic jams and lot of time to kill, I did some scrambling of the registration numbers of the cars in front of me. I ...
1
vote
1answer
42 views

Minimizing a sum given variables

I have this expression $$ax - b\left\lfloor\frac{cx}{m}\right\rfloor$$ Variables $a, b, c, m$ are known/given positive integers, and $x$ is an unknown integer with bounds $1 \leq x \leq m-1$. I ...
17
votes
0answers
213 views
+50

Finding primes so that $x^p+y^p=z^p$ is unsolvable in the p-adic units

On my number theory exam yesterday, we had the following interesting problem related to Fermat's last theorem: Suppose $p>2$ is a prime. Show that $x^p+y^p=z^p$ has a solution in $\mathbb{Z}_p^{\...
0
votes
1answer
474 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
1
vote
1answer
28 views

How many more legs than seats are in the leftover inventory (use modular-arithmetic)?

I have difficult with this problem, and appreciate any help. The Seats R Us factory produces chairs with four legs and stools with three legs. The seats and legs are the same for both chairs and ...
2
votes
2answers
36 views

Find two integers between 1 and 100

Can anyone help me with this? Thank you very much! Problem: Find two integers between 1 and 100 such that for each: a) if you divide by 4, the remainder is 3; b) if you divide by 3, the remainder ...
1
vote
1answer
33 views

What is the value of $N$ in a three-digit number $1N1$?

I don't know how to solve this problem. This is as far as I can go. $$\frac{1N1}{N}=2N+5$$ Then what should I do from there? Any help is highly appreciated. If a three-digit number of the form $...
2
votes
4answers
101 views

Is this possible to solve through algebra?

$$150 \equiv 17 \mod x, \qquad 100 \equiv 5 \mod x $$ Solve the simultaneous equation? Is this even a simultaneous equation? How do I find the value of $x$ too? I was doing a question and came up ...
3
votes
1answer
27 views

Determine the quadratic character of $293 \bmod 379$.

Determine the quadratic character of 293 mod 379. Did several other problems like this with 3, 5, 60, -1 and 307 all mod 379 but still having a tough time with this problem. I can post up work from ...
0
votes
1answer
32 views

Solving algebraic equations with modulus [closed]

How do I solve for 'b' given: $1 \equiv a\pmod{2} \\ a=\frac{b-1}{3}$
1
vote
1answer
35 views

Is there an integer z such that $255z\equiv 7\pmod {633}$?

I used the extended euclidean algorithm to "Find integers x and y such that $633x + 255y = 6$, or explain why none exist." And found that $6x = -58$ and $y = 144$. Now I'm stuck on the follow up ...
1
vote
0answers
42 views

Use modular-arithmetic to solve a scheduling problem

Can anyone help me with this? I know the problem is related to mod, but I don't know how to solve it using modular-arithmetic. Three professors start to teach math on the first Monday, Tuesday, ...
0
votes
1answer
53 views

Alternate way of showing infinitude of primes of the form $4m+1$

I would like to know if my approach is valid. I want to show that there are infinitely many primes of the form $4m+1$. Assume the contrary, and denote each of these primes by $p_{i}$ with $i \in \{1,...
8
votes
2answers
203 views

Last digit of $3^{459}$. [duplicate]

I am supposed to find the last digit of the number $3^{459}$. Wolfram|Alpha gives me $9969099171305981944912884263593843734515811805621702621829350243852275145577745\\...
6
votes
5answers
236 views

Calculate $121^{199} \mod 300$

Using Fermat's little theorem I proved that $$121^{199} = 121^{39} \mod 300$$ (as $\phi(300)$ is $80$) but I don't think I can leave it like this. My question being how can I solve $121^{39}\...
3
votes
8answers
284 views

Calculate the last digit of $3^{347}$

I think i know how to solve it but is that the best way? Is there a better way (using number theory). What i do is: knowing that 1st power last digit: 3 2nd power last digit: 9 3rd power last digit: ...
0
votes
2answers
46 views

Which of the following will give a remainder of 1?

Which of the following will give a remainder of $1$ ? $1$. $2^{100}$ divided by $7$ $2$. $2^{110}$ divided by $11$ $3$. $3^{140}$ divided by $11$ $4$. $12^{112}$ divided by $113$ Could someone ...
2
votes
4answers
63 views

Solve $x^2+x+1\equiv0\pmod5$

Solve: $$x^2+x+1\equiv0\pmod5$$ My attempt: Our proffesor told us that if we have $ax^2+bx+c\equiv\pmod p$ we need to multiply by $4a$, to get form of $(\text{ something})^2\equiv D\pmod p$. $...
0
votes
2answers
20 views

Number of solutions for $a$ of $x^2\equiv a \pmod3$

Find the all the numbers $a$ such that for $x^2\equiv a \pmod3$ there is: A. exactly one solution. B. two solutions. C. three solutions. D. no solutions. My attempt: $$1^2\...
0
votes
2answers
60 views

If $b^2 \equiv 1 \pmod 3$, is it possible to have $\sigma(b^2) \equiv b^2 \pmod 3$?

The title says it all. Let $\sigma(N)$ denote the sum of the divisors of the positive integer $N$. To paraphrase my question: If $3 \mid \left(b^2 - 1\right)$, is it possible to have $3 \mid \...
1
vote
2answers
58 views

Find the last digit of $66^5$

Find the last digit of $66^5$. This is how I solved the problem: $66^5=6^5*11^5$ (mod 10) = $6^5*1^5$ (mod 10). I have two questions. First, what is wrong with my method? I get different answer from ...
1
vote
5answers
3k views

Which of the following are complete residue systems modulo $11$?

Which of the following are complete residue systems modulo 11? $(a)\quad 0,1,2,4,8,16,32,64,128,256,512$ $(b)\quad 1,3,5,7,9,11,13,15,17,19,21$ $(c)\quad 2,4,6,8,10,12,14,16,17,20,22$ $(d)\quad ...
2
votes
4answers
92 views

how to solve $x^{113}\equiv 2 \pmod{143}$

I need to solve $x^{113} \equiv 2 \pmod{143}$ $$143 = 13 \times 11$$ I know that it equals to $x^{113}\equiv 2 \pmod{13}$ and $x^{113}\equiv 2 \pmod{11}$ By Fermat I got 1) $x^{5} \equiv 2 \pmod{...
2
votes
4answers
69 views

Find smallest $x$ such that $x=59 \pmod {60}$ and $x=1 \pmod 7$

Is a simple way to solve the problem? The method I used is to list all numbers from equation (1) and then see which one give remainder $1$ when divided by $7$. This doesn't seems a very smart way. ...
3
votes
1answer
112 views

Can it be proven using congruence?

We now that $a^3 +b^3=c^3$ has no solution if $a,b,c\in\mathbb{N}$(thus non of $a$, $b$ or $c$ can be zero). Well I want to know whether this can be proven using congruency(Like how we can prove that ...
1
vote
4answers
60 views

$777^{401} \pmod {1000}$ is?

here's an arithmetic question : find the last $3$ digits of $777^{401}$. I don't know where to start. The chinese remainder theorem gives a double congruence modulo $8$ and $125$ but I don't think ...
3
votes
2answers
205 views

Determination of the last two digits of $777^{777}$

May I know if my proof is correct? Thank you. This is equivalent to finding $x$ such that $777^{777} \equiv x \pmod{100}.$ By Euler's theorem, $777^{\ \psi(100)} =777^{\ 40}\equiv 1 \pmod{100}$. ...
3
votes
4answers
108 views

Find remainder when $777^{777}$ is divided by $16$ [duplicate]

Find remainder when $777^{777}$ is divided by $16$. $777=48\times 16+9$. Then $777\equiv 9 \pmod{16}$. Also by Fermat's theorem, $777^{16-1}\equiv 1 \pmod{16}$ i.e $777^{15}\equiv 1 \pmod{16}$. ...
1
vote
4answers
127 views

Find the remainder when $45!$ is divided by $47$?

Find the remainder when $45!$ is divided by $47$? My approach I am using Wilson's theorem to solve the problem. I reduced the expression into ($47$-$1$-$1$)!/$47!$=$(47$-$1$)/$47$!-$1$/$47!$=-$1$-$...
0
votes
1answer
58 views

How to find reminder of $m^{x}$ divided by $n$ using Euler's and Fermat's little theorem [duplicate]

How do you find reminder of $m^{x}$ divided by $n$ using Euler's and Fermat's little theorem? Can anyone show me step-by-step how to apply Fermat's little theorem and Euler's theorem? Example: What ...
1
vote
1answer
251 views

Remainder when dividing $13^{3530}$ with $12348$ [duplicate]

Find the remainder when dividing $13^{3530}$ with $12348$. How do I solve these type of exercises? I know there's some algorithm for solving them, I just haven't found a concrete example. Could ...
2
votes
1answer
750 views

Find the remainder when $10^{400}$ is divided by 199?

I am trying to solve a problem Find the remainder when the $10^{400}$ is divided by 199? I tried it by breaking $10^{400}$ to $1000^{133}*10$ . And when 1000 is divided by 199 remainder is ...
2
votes
2answers
36 views

What are the valid deductions of a congruence equation?

So I was just sitting here, doing math, and I came over this: $9+16a\equiv 12 \pmod 5$ Obviously, through some simple manipulations: $9+16a-15a-9\equiv 12-9 \pmod 5$ $a\equiv 3 $ And that is a ...