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

learn more… | top users | synonyms (1)

0
votes
1answer
47 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
30 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
61 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$ [on hold]

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
39 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
274 views

Is there something interesting about $373857714078$? [closed]

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
44 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
89 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
32 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
119 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
30 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
51 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
20 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
52 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
21 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
40 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
36 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
49 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
60 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
412 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
36 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
69 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
57 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
50 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
67 views

Find the prime number [closed]

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
25 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
54 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? [closed]

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
82 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
49 views

Find all three numbers [closed]

Find all I three numbers, that can be divided to $11$, and the result equal to sum of square every digit from digits that number I tried but, I couldn't complete.
0
votes
2answers
40 views

Prove that $a+6b+4$ is full square. [closed]

Let $b=333...33, a=999...99$ where $a$ has $2n$ digit, $b$ has $n$ digit Prove that $a+6b+4$ is full square.
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 ...
0
votes
0answers
18 views

Find number of solution of a linear congruence in terms of ceiling function? [closed]

For $v\in \{0, 1,..., A-1 \}$ and $i\in \{0,1,...,B-1\}$, the number of solutions of the congruence $v\equiv i \pmod{B}$ is given by $\lceil \frac{A-i}{B} \rceil$. How to prove this statement?
3
votes
3answers
49 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
49 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
379 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
54 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
58 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
26 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
41 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?