# Tagged Questions

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$.

49 views

### Solve $276 x\equiv 90\pmod {666}$

Solve $276 x\equiv 90\pmod {666}$ I found using Euclidean algorithm that $\gcd (276,666)=6$ then I divided by $6$ and I got: $$46x\equiv 15\pmod {111}$$ and I found that $\gcd(46,111)=1$ using ...
77 views

### Prove that there are infinitely many values of $n$ for which $\phi(n)=\frac{n}{2}-1$

I know that $\phi(n)=\frac{n}{2}-1$ is actually one of the strong lines on a plot of Euler's phi function, the other being $\phi(n)=n-1$. However I don't know how to go about proving it. Where should ...
12 views

13 views

### Find all Dirichlet characters modulo $p$

In my elementary number theory class we define the following: Let $p$ be a prime, and let $\mathbb{Z}_p^*$ relatively prime residues modulo $p$. A Dirichlet character modulo $p$ is defined as a ...
32 views

### Find the remainder of $\sum_{i=0}^{99} 2^{i^2}$ when dividing by 7 and determine if the quotient is even or odd

I've recently had this problem in an exam and couldn't solve it. Find the remainder of the following sum when dividing by 7 and determine if the quotient is even or odd: $$\sum_{i=0}^{99} 2^{i^2}$$ ...
23 views

### A question on “law of congruence of modulus”

I have a quick question about the law of congruence of modulus, which states "Let $a•b≡a•c \,(\mod m)$, where $a$ is not equivalent to $0$,$\mod m$. We can cancel $a$ only when $a$ and $m$ are ...
52 views

56 views

### If the sum of two $p$th powers is divisible by $p$, then it is divisible by $p^2$

If $p > 2$ is a prime and $p | (x^p + y^p)$, then show that $p^2 | (x^p + y^p)$ I have been stuck on this problem for a while now. (Though my textbook is prone to mistakes so the original ...
22 views

### Show $x^k \equiv a\space(mod\space p)$ has at most one solution when $k$ and $p-1$ are coprime

Let $p$ be a prime, and $k\in \mathbb{N}$ such that $hcf(k, p-1) = 1$. If $a$ is an integer then show that $x^k \equiv a \space\text{mod}\space p$ has at most one solution. So far i've tried assuming ...
19 views

### Field of the form $\{a+bi|a,b\in \mathbb{F}_p\}$

Artin, Algebra, Chapter 3, Ex 1.11 Consider whether the set of symbols $\{a+bi|a,b\in\mathbb{F}_p\}$ forms a field, if the laws of composition are made to mimic addition and multiplication of complex ...
76 views

### Finding an Elliptic Curve with 103 points

I am trying to solve the following problem: Find an elliptic curve over F101 with 103 points. I know all of the equations when needing to find alpha, and beta and all that when I am given two points ...
53 views

### Use of modular arthemitic to prove identity

While studying primes that are either $2^n+1$ or $2^{n}-1$, I noticed this relationship. $2^{(n-1)/{2}}-(-1)^{(n^{2}-1)/{24}}\equiv 0\mod n$ iff $n$ is prime for $n\ge5$. My question is, how can I ...
8 views

21 views

### Proof involving two's complement arithmetic of binary numbers

I have a "clock" - a 32-bit unsigned number - that wraps around from $4,294,967,295$ ($2^{32}-1$) back to $0$. At point 'A' in time, I stamp the clock into a variable - call it $x$. Later, at point 'B'...
15 views

56 views

### Prove that $11^{2n}+5^{2n+1}-6$ is divisible with $24$ for $n∈ℤ^+$

Prove that $11^{2n}+5^{2n+1}-6$ is divisible with $24$ for $n∈ℤ^+$ I've been trying to solve it by using modulo; $11^{2n}+5^{2n+1}-6≡ (11^2 mod24)^n + 5*(5^2mod24)^n-6 = 1^n + (5*1^n)-6 = 0$ Is this ...
44 views

### Finding modular inverse of every number mod 26?

I am looking at cryptography, and need to find the inverse of every possible number mod 26. Is there a fast way of this, or am i headed to the algorithm every time?
29 views

### How do i prove that $Z_n$ is a subring of $Z_m$ using the subring test?

Let $n, m \in Z^+ \setminus {1}$. Assume $n|m$. How do i prove that $Z_n$ is a subring of $Z_m$ using the subring test? Do i just have to follow the 3 conditions for the subring test? or there ...
21 views

### Discrete Math - RSA Encryption problem

I am doing practice problems for my upcoming final exam, and am having trouble with this RSA encryption problem. If any one could check to see if i did these correctly, it would be greatly appreciated....
71 views

### How do I find the smallest positive integer $a$ for which $a^n \equiv x \pmod{2^w}$?

$x$ is fixed odd positive integer value. $n$ and $w$ are fixed positive integer values. $a$ is positive integer value. I am interested for $n=41$ and $w=160$, but would appreciate a general algorithm....
27 views

Given large $n\in\Bbb N$ is there many $a,b\in(n,2n)$ with $\gcd(a,b)=1$ and $q,r\in(n^4,2n^4)$ with $\gcd(a,bq)=\gcd(ar,b)=1$ and $c,d\in(n^3,2n^3)$ with $-n<-x=q\bmod c,-y=r\bmod d<0$ with $\... 1answer 43 views ###$3x + 1 = 2^i$only has integer solutions when$i$is even I came across this question while looking at powers of 2 and investigating number theory. I found it quite interesting, unfortunately I would say that my skills in number theory are far too primitive ... 2answers 47 views ### Why is this valid for modulus? My teacher asked if this statements was valid: $$37 + 50 \equiv 27 \pmod {60}$$ Which is basically $$87 \equiv 27 \pmod {60}$$ and he said this is true. But how? I know that$87 \bmod {60}$is$...
I'm trying to compute such number: $a \equiv 0 \pmod m$ and $a\equiv0 \pmod 3$. $a$ can be large but divisible by $3$ and $m$ is not guaranteed to be coprime with $3$. The solution which I came up ...
I'm playing around with this problem. $$x^{2} - 2x + 10 \equiv 7 \ \text{mod} \ 6$$ Find the equivalence class(es) in $\mathbb{Z_{6}}$ solving this. The following doesn't work out: \$...