Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

1
vote
1answer
18 views

classification of groups of order $4p, p\ge 5$, need help finding automorphism

So I've been working on this problem for my qual prep class, and I have it all down except for one detail. I'm doing it by semidirect products, and with the Sylow $p$ group normal, choosing the ...
1
vote
1answer
40 views

Showing certain sum as a Riemann-Stieltjes integral

Let $e(\beta) = e^{2 \pi i \beta}$. I am reading an article, where the author defines the following sum $$ S(N) = \sum_{0 \leq x \leq N, x \equiv g (mod \ q)} \Lambda(x) e(f(x) \alpha), $$ where $f$ ...
0
votes
0answers
74 views

Rewriting $\#\{ b (\text{mod } 2n) | b^2 = D (\text{mod 4n}) \}$

Let $R^*(n) = \#\{ b (\text{mod } 2n) | b^2 = D (\text{mod 4n}) \}$ and $n = 2^{r_0} p_1^{r_1} \ldots p_s^{r_s}$ with $p_i$ prime and odd. Then we can rewrite $R^*(n)$ as $R^*(n) = R^*(2^{r_0}) \cdot ...
2
votes
4answers
78 views

Solving $x^2=17\pmod{128}$

I'm attempring to solve a congruence $x^2 \equiv 17\pmod{128}$ but not quite sure how to go about it. I see that $128 = 2^7$, but the Chinese Remainder Theorem doesn't apply to $\gcd > 1$. I found ...
8
votes
5answers
59 views

Is it allowed to define a number system where a number has more than 1 representation?

I was just curious; is it allowed for a number system to allow more than one representation for a number? For example, if I define a number system as follows: 1st digit (from right) is worth 1. 2nd ...
1
vote
0answers
34 views

sextic reciprocity and divisibility question

Regarding the question if $p|(2^{2(p-1)/6}+2^{(p-1)/6}+1) $ where $p$ is a prime of the form $7\mod 8 $ That is how far I got: $2^{(p-1)/6} \mod\ p\equiv x $ if the solution of $x^6\ mod\ ...
5
votes
2answers
63 views

Solve $\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{pq}$

For $x,y\in\mathbb{N}$ how many ordered pairs $\left(x,y\right)$ satisfy $\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{pq}$ where $p,q$ are distinct primes?
1
vote
1answer
53 views

Is there any algorithm or something to solve $\phi\left(x\right)=n$ [closed]

solve for x, $\phi\left(x\right)=12$ where $\phi$ is euler's totient function($\phi\left(n\right)$ is the number of numbers less than n satisfying $hcf\left(n,i\right)$ with $1\leq i<n$. I'm ...
1
vote
0answers
45 views

Verification of Basic Proof in Spivak Calculus (Induction)

I have began working through Spivak's Calculus book and trying to do the problems at the end of the chapters. I am rather new to proof, so forgive the naivety of this type of question. I am wanting ...
0
votes
3answers
45 views

How to calculate this expression and get an integer number?

Hello there I don't have idea how to calculate this: $$\left[\frac {116690151}{427863887} \times \left(3+\frac 23\right)\right]^{-2} - \left[\frac{427863887}{116690151} \times \left(1-\frac ...
1
vote
1answer
94 views

how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime?

Given that $$U_n=\underbrace{1\cdots1}_{n\text{ times}}$$ and $n >2$, how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime? Because $U_m= ...
-1
votes
0answers
34 views

Pythagorean triangle with in-radius r: problems

If there is no odd prime divisor of $r$, prove that there is only one Pythagorean triangle with in-radius r. If $r=pq$, the product of two distinct primes, prove that there are four ...
1
vote
7answers
121 views

What is the last digit of $2003^{2003}$?

What is the last digit of this number? $$2003^{2003}$$ Thanks in advance. I don't have any kind of idea how to solve this. Except that $3^3$ is $27$.
0
votes
3answers
33 views

Problems on Pythagorean triangle

Show that there is one (no) Pythagorean triangle whose sides are in arithmetic (geometric) progression. The problem has two parts. There is one Pythagorean triangle whose sides are in arithmetic ...
1
vote
2answers
45 views

Show that $a^{16}-b^{16}$ is divisible by $133$ if $a$ and $b$ are both prime to $85$

Show that $a^{16}-b^{16}$ is divisible by $133$ if $a$ and $b$ are both prime to $85$ Since $(85, a)=1(17,5)$ and $(85, b)=(17,5)$ then $a^{16}-1\equiv (mod ~17)$, $a^{4}-1\equiv (mod~ 5)\implies ...
3
votes
2answers
41 views

Find the last two digits of $33^{100}$

Find the last two digits of $33^{100}$ By Euler's theorem, since $\gcd(33, 100)=1$, then $33^{\phi(100)}\equiv 1 \pmod{100}$. But $\phi(100)=\phi(5^2\times2^2)=40.$ So $33^{40}\equiv 1 ...
3
votes
4answers
52 views

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

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}$. ...
0
votes
1answer
36 views

Find the missing digit in the number 23104*791

Find the missing digit in the number $23104*791$ if (i) it is divisible by $11$, (ii) it is divisible by $13$, (iii) it is divisible by $63$. (i) $23104*791=231 ...
0
votes
1answer
23 views

Show that $x_1x_2\cdots x_n (mod~ m)\equiv (x_1 (mod~m)\cdot x_2 (mod~m)\cdots x_n (mod~m))(mod~ m)$

Show that $x_1x_2\cdots x_n (mod~ m)\equiv (x_1 (mod~m)\cdot x_2 (mod~m)\cdots x_n (mod~m))(mod~ m)$ I know that $a\equiv b (mod ~ m)$, $c\equiv d (mod ~m)$ implies $ac\equiv bd (mod ~m)$ but how ...
4
votes
2answers
56 views

Use Wilson theorem to show that $63! + 1 \equiv 0 \mod ~ 71$

Use Wilson theorem to show that $63! + 1 \equiv 0 \mod ~ 71$. 71 is prime then Wilson theorem says that $(71-1)!+1=0 \mod ~ 71$ i.e $70!+1\equiv 0 \mod ~ 71$ then how to proceed further?
3
votes
7answers
85 views

What is the remainder when $6\times7^{32} + 7\times9^{45}$ is divided by $4$?

What is the remainder when $6\times7^{32} + 7\times9^{45}$ is divided by $4$ ? $7 \equiv 3 \pmod 4$ $7^2 \equiv 9 \pmod 4\equiv 1 \pmod 4$ $(7^2)^{16} \equiv 1^{16} \pmod 4$ i.e $7^{32} ...
2
votes
1answer
22 views

Find all values of $p$ such that $ax^2+bx+c \equiv 0 (\bmod p)$ have solution

Is there a general way to find all values of $p$ such that the congruence $ax^2+bx+c \equiv 0 (\bmod p)$ have solution, we can assume that $ax^2+bx+c =0 $ have solution.
-1
votes
1answer
46 views

If p is an odd prime, show that $p^2 \equiv 1 \pmod 8 $

If p is an odd prime, show that $p^2 \equiv 1 \pmod 8 $. I know that odd numbers are of the form $2k \pm 1$. Then $p^2=(2k \pm 1)^2= 4k^2 \pm 4k +1$. But it does not help to solve.
1
vote
1answer
37 views

Find out a process to generate pairs of distinct positive integer $m$, $n$ with $\phi(m) = \phi(n)$.

Find out a process to generate pairs of distinct positive integer $m$, $n$ with $\phi(m) = \phi(n)$. Attempt: The pairs $m=1, ~ n=2$; $m=3, ~n=4$ satisfy the problem. But I need a ...
-1
votes
2answers
50 views

Is this problem correct? [duplicate]

I have found another problem in my book. I have to prove that $$2^{70}+3^{70}$$ is divisible by 13. But I have proven that $2^{70}\equiv 12 (mod 13)$ and $3^{70}\equiv 3 (mod 13)$ so it is ...
1
vote
2answers
63 views

How can I find the remainder?

How can I find the remainder when $$(12371^{56}+34)^{28}$$ is divided by $111$. I have tried congruences modulo $111$ but without any success.
4
votes
6answers
433 views

Elementary number theory - prerequisites

Since summer comes with a lot of spare time, I've decided to select a mathematical subject I want to learn as much as possible about over the next three months. That being said, number theory really ...
0
votes
1answer
79 views

Can this expression be made true ? 2 _ _ _ _ = 2015

Make this expression true: 2 _ _ _ _= 2015 The underscores must be replaced by any 2 of of the operational symbols +, - , x, / (divide). And any 2 of the digits 0,1,2..9. So, you basically need 2 ...
0
votes
1answer
61 views

About the vertices of a regular polygon in the plane having rational coordinates [closed]

I have to prove that, except in the case $n=4$, the vertices of a regular $n$-agon in the Euclidean plane cannot have all rational coordinates $(x,y)$. Some idea?
1
vote
3answers
61 views

Determining the relative size of $a^n$ and $b^m$ without using logarithms

Example, which is larger $ 17^{105} $ vs $ 31^{84} $? Make the deternimination without resorting to logs, or Excel either.
1
vote
1answer
24 views

$p$ and $r$ are primes greater than $2$. $p+r$ vs $p+2r$, which could be a prime number?

For $p+2r$, a example would be $3$ and $5$. Since $6+5 = 11$, I am led to believe $p+2r$ to be the right answer. But I don't know how it works?
1
vote
1answer
52 views

Addition of points on elliptic curves over a finite field

I have found the following formulas for the coordinates of $P+Q$ given that $P = (x_{1}, y_{1})$ and $Q = (x_{2}, y_{2})$ are points on a general curve $y^2 = x^3 + ax + b$ over $\mathbb{R}$: $$P + Q ...
0
votes
1answer
27 views

Factor RSA number $n$.

An RSA number $n=p\cdot q$, where $q=2\cdot d +1$, $d$ an odd integer, is given. Assuming $a \in \mathbb{Z}_n$ with $a^4=1$ and $a^2 \neq 1$. How can this information lead to finding $p$ and $q$? I ...
4
votes
2answers
57 views

Irrational numbers, induction

I have $\sqrt[3]{2}^{2^n}$. Can I prove that this number is irrational by showing that $3$ does not divide $2^n$?
4
votes
5answers
100 views

Prove every integer is of the form $5k+r$ with $0\le r<5$

I have came across this question from my text book: Prove or disprove: any integer $n$ is of the form: $5k$, $5k + 1$, $5k + 2$, $5k + 3$ or $5k + 4$ for some integer $k$. I'm not sure what would be ...
1
vote
1answer
35 views

$r! \equiv (−1)^k \pmod p$

Suppose that p ≡ 3 (mod 4) and $r = \frac {p-1}2$ Show that $r! \equiv (−1)^k \pmod p$ where k is the number of non-quadratic residues modulo p which are smaller than $\frac p2$ I know from ...
0
votes
1answer
30 views

Show that $(r!)^2 ≡ (−1)^{r−1} \pmod p$ [duplicate]

I need to prove that if p is an odd prime and $r = (p-1)/2$ then $(r!)^2 ≡ (−1)^{r−1} \pmod p$ I think it has something to do with gauss's lemma ...
1
vote
1answer
62 views

Prove that $\sin{\frac{2\pi x}{x^2+x+1}}=\frac{1}{2}$ has no rational roots.

Show that the following equation has no rational roots. $$\sin{\frac{2\pi x}{x^2+x+1}}=\frac{1}{2}$$ This is what I've tried: $$\left ( \frac{2\pi x}{x^2+x+1}=\frac{\pi}{6}+2k\pi ...
1
vote
1answer
31 views

Prove/disprove the following asymptotic bound

Indicating with $p$ and $q$ prime numbers, is it true that for $x\rightarrow\infty$ $$ \sum_{\substack{p\leq x \\ p\equiv 1 ...
3
votes
3answers
51 views

Finding the last digit of $7^n$, $n\ge 1$.

I have noticed a cycle of 7,9,3,1. Meaning: $7^1\equiv 7\pmod {10}, 7^2\equiv 9\pmod {10}, 7^3\equiv 3\pmod {10},7^4\equiv 1\pmod {10}, 7^5\equiv 7\pmod {10}$ and so on. Therefore, if $n=4k+1$ the ...
2
votes
3answers
54 views

Proof for $\left\lfloor\frac 1j\left\lfloor\frac nk\right\rfloor\right\rfloor=\left\lfloor\frac n{jk}\right\rfloor$

Problem: For positive integers $n,j,k$, prove that the following holds: $$\left\lfloor\frac 1j\left\lfloor\frac nk\right\rfloor\right\rfloor=\left\lfloor\frac n{jk}\right\rfloor$$ I simply ...
4
votes
2answers
403 views

Is there any simple trick to solve the congruence $a^{24}\equiv6a+2\pmod{13}$?

Which of the following primes satisfy the congruence $$a^{24}\equiv6a+2\pmod{13}$$ 1) 41 2) 47 3) 67 4) 83 I am interested in Theorem statement, corollary, or Trick or Logic which solves this ...
2
votes
4answers
58 views

Question on Math.floor on negative number [closed]

why do these return different results? Math.floor(-1735)=-1735 Math.floor(-17.35*100)=-1736
1
vote
2answers
63 views

solve $x^2 \equiv 24 \pmod {60}$

I need to solve $x^2 \equiv 24 \pmod {60}$ My first question which confuses me a lot - isn't a (24 here) has to be coprime to n (60)??? most of the theorems requests that. what i tried - $ 60 ...
1
vote
2answers
29 views

How to find the indexes given the element index in a vector?

I have a vector $\mathbf{x} = [x_{11}, x_{12}, \ldots, x_{1n}, x_{21}, x_{22}, \ldots, x_{2n}, \cdots, x_{m1}, x_{m2}, \ldots, x_{mn}]^T$ of size $m\cdot n$. My problem is this: Given an index ...
0
votes
3answers
42 views

Is it true that $x \nmid (q-1) \implies 2^x \not \equiv 1 \mod q$

If $q$ is a prime number, then from little fermat theorem it is known that $$2^{q-1} \equiv 1 \mod q$$ My doubt is that If $x \nmid (q-1)$ then $2^x \not \equiv 1 \mod q$ is true statement or not? ...
0
votes
0answers
20 views

Function for the number of divisor of a number [duplicate]

Is there a formula/function that given any $n$ produces the number of divisors of $n$ ? And has that something to do with Euler function?
0
votes
3answers
27 views

binary representation of integers congruent 1 and 3 modulo 4

Let $k=b_nb_{n-1}\ldots b_3b_2b_1b_0$ be the binary representation of an odd positive integer. Prove: If $k\equiv 1 \mod 4$ then $b_1=0$. If $k\equiv 3 \mod 4$ then $b_1=1$. I think that to prove ...
2
votes
3answers
52 views

Let $z \in \Bbb Z_m$, when is $z^2 \equiv 1$?

Let $z \in \Bbb Z_m$. When is $z^2=1, (z\neq1)$? I know that for $m$ prime, $z=p-1$ is it's own inverse, but what about nonprime $m$? Is $p-1$ the only self inverse element in $\Bbb Z_p$ ?
0
votes
1answer
63 views

When does Fermat's little theorem not hold for coprimes $a$ and $p$ , but $p$ being non-prime and why?

When does Fermat's little theorem not hold for coprimes $a$ and $p$, but $p$ being non-prime and why? I tested some non-prime values of $p$ and it seems to still hold.