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

learn more… | top users | synonyms (1)

3
votes
3answers
63 views

Calculating remainder of $666^{666}$ when divided by $1000$.

I want to calculate the remainder of $666^{666}$ when divided by $1000$. But for the usual methods I use the divisor is very big. Furthermore 1000 is not a prime, 666 is a zero divisor in ...
5
votes
3answers
83 views

Perfect powers of successive naturals: Can you always reach a constant difference?

I was thinking about what happens if you take a sequence of consecutive squares, for example 1,4,9, 16. Taking the differences gives you another sequence, 7,5,3. And taking the differences between ...
7
votes
1answer
66 views

Prove that $2AB$ is square

Let $$A= 1! \cdot 2! \cdot 3! \cdots 1002!$$ $$B= 1004!\cdot 1005! \cdots 2006!$$ Prove that $2AB$ is square. Help guys, I tried, I really did but I couldn't.
1
vote
1answer
34 views

Square numbers in the form $1+4y$

I want to solve the equation $y+x=x^2$: $$ x^2-x-y=0 \\ x_{1;2}=\frac{1\pm \sqrt{1+4y}}{2} $$ However I want the solutions to be only natural numbers; the question then turns to find values of $y$ ...
2
votes
2answers
40 views

What is the logic/theorem/derivation behind finding the exponent of p in n! By [n/p] + [n/p^2] + [n/p^3] + …? [duplicate]

The exponent of prime number of 3 in 100! is 48. It means 100! is divisible by $3^48$ $$E_3(100!) = \left\lfloor\frac{100}3\right\rfloor + \left\lfloor\frac{100}{3^2}\right\rfloor + ...
-2
votes
2answers
46 views

Prove that to any three numbers positive integers [on hold]

Prove that for any three positive integers, following equality holds $$\operatorname{lcm}(ab , bc , ca ) \cdot \gcd(a , b, c )=abc$$
4
votes
3answers
318 views

Students in a class, girls sitting with boys and boys sitting with girls

This is a very interesting word problem that I came across in an old textbook of mine. So I mused over this problem for a while and tried to look at the different ways to approach it but unfortunately ...
6
votes
0answers
110 views

What is known about the sum $\sum\frac1{p^p}$ of reciprocals of primes raised to themselves?

Consider the following series: $$\sum_{p\in\mathcal{P}}\frac{1}{p^p}$$ where $\mathcal{P}$ is the set of all prime numbers: $\mathcal{P}=\{2,3,5,7,11,13,\ldots\}$. My question is: Is this a ...
3
votes
3answers
59 views

Is it necessary and sufficient that $6$ divides $n^2$ for the positive integer $n$ to be divisible by $6$? [on hold]

As the title suggests, is it a necessary and sufficient that $6$ divides $n^2$ for the positive integer $n$ to be divisible by $6$? Like, I understand the dictionary definitions of necessary and ...
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 ...
0
votes
0answers
19 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
30 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
71 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 ...
-1
votes
0answers
25 views

Using the extended euclidean algorithm to find Bezout coefficients [on hold]

I need help seeing how to use the extended euclidean algorithm to find integers $s,t$ such that $135s + 59t = \gcd(135, 59)$.
5
votes
5answers
46 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 ...
0
votes
1answer
42 views

Proving that a real number is a non-negative integer. [on hold]

Let $n$ and $k$ be integers such that $0\le k<n$ and $n\ge 2$. Let P and Q be the sets of all distinct prime numbers dividing $(n-k)$ and $(n+k)$ respectively. Let $r=\prod_{p\in P}(1-1/p)$ and ...
1
vote
0answers
25 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\ ...
6
votes
2answers
58 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?
2
votes
1answer
46 views

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

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
35 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 ...
14
votes
2answers
247 views

Is there something interesting about $373857714078$? [on hold]

On a site, someone asked which number is most interesting and I answered, "Every number is interesting. Give me a number and I shall tell you why it is!". Now some guy took it literally, and gave me ...
0
votes
3answers
43 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
84 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= ...
0
votes
0answers
31 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
114 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
29 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
37 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
40 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
49 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
34 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
19 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
51 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
78 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
20 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
39 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
34 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
48 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
57 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.
5
votes
6answers
402 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
0answers
33 views

Nice statements about the “opposite properties” of $0$ and $1$.

Some of $0$ and $1$'s properties as natural numbers are pleasingly opposite of one another, such as: 1a.) $0$ has infinitely many divisors, but no (non-zero) multiples. 1b.) $1$ has infinitely many ...
0
votes
1answer
67 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
55 views

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

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
60 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
23 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
48 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 ...
-7
votes
2answers
66 views

Find the prime number [on hold]

Find all prime numbers $a,b,c$ and positive integers $k$ satisfying the equation $a^2 + b^2 + 16c^2=9k^2+1$. I tried but I didn't came to any result.
0
votes
1answer
24 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
53 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$?
0
votes
0answers
23 views

How many tiles are Symmetrical? [on hold]

We have a tape of type $1 * 2015$ had tile from tiles unit square in four different colors so as not exceed two tile of the same color (tile unit square, any tile from type $1*1$) How many tiles are ...
3
votes
4answers
79 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 ...