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

learn more… | top users | synonyms (1)

8
votes
2answers
305 views

Proving that $n^2-l$, $n^2$ and $n^2+l$ can't all be perfect squares

I tried to write a proof and used the argument that if $n^2$ is a perfect square, $n^2-l$ and $n^2+l$ can't both be perfect squares. However, I can't find a proof for this statement. Can you help me ...
1
vote
2answers
46 views

Linear congruences $2X\equiv9\pmod{26},\pmod{25}$

May double that of a natural number let rest $9$ when divided by $26$? And when divided by $25$? I tried: $$2X\equiv9\pmod{26}$$ As $(26,2)=2$ and $2\nmid9$ then the congruence linear not ...
1
vote
1answer
54 views

Cyclicity of finite group

If $g$ is a primitive root of $p$ (i.e. $\mathbb{F}_p^{\times}=\langle g \rangle$) show that two consecutive powers of $g$ have consecutive least residues. That is, show that there exists $k$ such ...
1
vote
3answers
228 views

If $p$ is prime, then the kth root of $p$ is irrational, $(p^{\frac 1k}) $, for any integer $k>1$, prove it's irrational by assuming it is rational [duplicate]

The $k^\text{th}$ root of $p$ is irrational, $(p^{\frac1k})$ , for any integer $k>1$, prove it's irrational by assuming it is rational. I've tried setting it equal to $\frac a b$ and then raising ...
5
votes
1answer
179 views

On a sum involving fractional part of an integer

I was interested in estimating the sum of the form $$ \sum_{j=1}^{N} \{ \sqrt{j} \}. $$ I was wondering if there is a reference or maybe some one could help me figure out what to do. Thanks! $\{ ...
2
votes
2answers
72 views

Squaring any odd number $k-2$ times produces $1$ modulo $2^k$

If $k>2$, show that if $a$ is odd, then $$a^{2^{k-2}}\equiv 1\pmod{2^k}$$ Being very honest, do not even know where to start!!
2
votes
5answers
1k views

Show that the sum of squares of four consecutive natural numbers may never be a square.

Show that the sum of squares of four consecutive natural numbers may never be a square. I know (and I have the proof) a theorem that says that every perfect square is congruent to $0, 1$ or $4$ ...
1
vote
0answers
50 views

Discriminating integer partitions

Given a fixed positive integer, say $n$, letn $P_n$ be the set all partitions of $n$, where each partition itself is a set i.e. order is discarded and each part is less than 5. Can we establish a ...
4
votes
4answers
357 views

Find the smallest natural number that leaves residues $5,4,3,$ and $2$ when divided respectively by the numbers $6,5,4,$ and $3$

Find the smallest natural number that leaves residues $5,4,3,$ and $2$ when divided respectively by the numbers $6,5,4,$ and $3$. I tried ...
0
votes
1answer
80 views

Let p be a prime. Prove that there are ϕ(p−1) many primitive roots mod p.

I'm new to number theory and the only proof I've been able to find is the one here http://math453spring2009.wikidot.com/lecture-24 however its a bit over my head, is there a more elementary way to go ...
15
votes
6answers
31k views

Modulo of a negative number

Consider the following expression: (a - b) mod N Which of the following is equivalent to the above expression? ...
1
vote
3answers
48 views

If $(m,n)=1$ and $mn=r^2$ for $m,n\in\mathbb{Z}^+$, prove that $m$ and $n$ are squares.

Honestly unsure how to proceed with this; I have some thoughts but don't know where to go with them. $(m,n)=1\Longrightarrow m\nmid n$ and $n\nmid m$. But $mn=r^2$, so $\frac{r^2}{mn}=1$, and $mn\mid ...
0
votes
1answer
43 views

Proof regarding GCD

I'm trying to prove that if $a,b$ are two primes between themselves then $a+b$ and $a^2+ab+b^2$ are also prime between themselves. That is, we have to prove that $\text{gcd}(a,b)=1\Rightarrow ...
5
votes
1answer
64 views

Is it true that if $n$ is even then $\sum_{k=1}^{n}(n \bmod k)<\frac{8}{45}n^2$?

Let $f(n,k)$ be the least non-negative integer such that $n\equiv f(n,k) \bmod k.$ $f(10,k)(k=1,2,\cdots,10)=0, 0, 1, 2, 0, 4, 3, 2, 1, 0.$ Hence $$\sum_{k=1}^{10}f(10,k)=1+2+4+3+2+1=13.$$ ...
1
vote
2answers
40 views

Simple notation question

Let A = {2, 3, 4, 6, 7, 9} and define a relation R on A as follows: For all x, y ∈ A, x R y ⇔ 3 | (x − y). Then 2 R 2 because 2 − 2 = 0, and 3 | 0. What does the ...
1
vote
1answer
328 views

Pisano periods of fibonacci mod

The wikipedia article on Pisano periods utilises the Binet's formula and quadratic residues to find $f(n)$ such that $F_n=f(n) \pmod{p}$ where $p$ is a prime number and $F_n$ is a Fibonacci number. ...
0
votes
1answer
69 views

How to simplify the following modulo operation

I am trying to find the modulo of an expression. All I know is that (a+b) mod N = ((a mod N) + (b mod N)) mod N How do I use it to simplify the following modulo ...
0
votes
2answers
107 views

Lattice property of coprime integers

I was reading on the Wikipedia page for coprime numbers that (for $a \gt b$), gcd($a,b$)$=1$ if and only if the diagonal connecting $(0,0)$ and $(a,b)$ does not cross through any lattice points ...
1
vote
3answers
87 views

Remainder when dividing $3^{10}+3^{10^2}+3^{10^3}+…+3^{10^{100}}$ by $7$

Determine the remainder of dividing $10^{10}+10^{10^2}+10^{10^3}+...+10^{10^{100}}$ by $7$ We have $10\equiv3\pmod7$ then ...
5
votes
3answers
98 views

To what divisors $a$ of $n$ can Euler's Theorem multiplied by $a$ be generalized, i.e. when is $a^{\phi(n)+1}\equiv a \pmod n$?

Euler's Theorem $$a^{\phi(n)}\equiv 1\pmod n,$$ which is valid only iff $a$ and $n$ are coprime, can be "generalized" a bit to $$a^{\phi(n)+1}\equiv a\pmod n, (*)$$ where some zero-divisors of $n$ are ...
2
votes
5answers
116 views

Given $n \in \mathbb{N}$ prove that a polynomial result gives a natural number.

A friend asked me this question: Prove that for every $n\in \Bbb N$ the next equation result: $\dfrac{n^3}{6}+\dfrac{n^2} {2}+\dfrac{n}{3}$ would be a natural number. My instincts were that i need ...
0
votes
1answer
676 views

remainder on division by 9 for a tricky number

What will be the remainder when $ 32^{32^{32}} $ is divided by 9? I was able to solve this by using the cyclicity of remainders when $2^{2^n}$ is divided by 9. For $n$ =even it gave remainder 7 ...
7
votes
2answers
270 views

Proof that:$ \sum\limits_{n=1}^{p} \left\lfloor \frac{n(n+1)}{p} \right\rfloor= \frac{2p^2+3p+7}{6} $ where $p$ is a prime and $p \equiv 7 \mod{8}$

Proof that:$ \sum\limits_{n=1}^{p} \left\lfloor \frac{n(n+1)}{p} \right\rfloor= \frac{2p^2+3p+7}{6} $ where $p$ is a prime number such that $p \equiv 7 \mod{8}$ I tried to separate the sum into ...
1
vote
3answers
127 views

Find remainder when $F(x)$ is divided by $P(x)$

Find the remainder when $F(x)=x^{276}+12$ is divided by $P(x)=x^2+x+1$?
1
vote
0answers
49 views

Ineqality regarding LCM of $1, 2, \ldots, n$

While going through F. Beukers proof of irrationality of $\zeta(3)$ I found the inequality $d_{n} < 3^{n}$ for all sufficiently large values of $n$ where $d_{n}$ denotes the LCM of all the numbers ...
4
votes
0answers
280 views

Crititism of the set-theoretic definition of natural numbers

A while ago I read in a book (or a paper?) that a very well-known mathematician (Saunders Maclane?) in his lectures used to mock the classical set-theoretical definition of natural numbers: 0 = {}, 1 ...
2
votes
2answers
97 views

What the rest of the division $1^6+2^6+…+100^6$ by $7$?

What the rest of the division $1^6+2^6+...+100^6$ by $7$? $1^6\equiv1\pmod7\\2^6\equiv64\equiv1\pmod7\\3^6\equiv729\equiv1\pmod7$ Apparently all the leftovers are $one$, I thought of ...
2
votes
2answers
231 views

F ind the seven solutions to $x^{7} \equiv 1 \ (mod \ 29)$

Use the fact that $2$ is a primitive root modulo 29 to find the seven solutions to $x^{7} \equiv 1 \ (mod \ 29)$ As $2$ is primitive root modulo $29$ then $$2^{28} \equiv 1 \ (mod \ 29) $$ ...
0
votes
0answers
39 views

the division $14^{256}$ by $17$ [duplicate]

What the rest of the division $14^{256}$ by $17$? $$14^2\equiv9\pmod{17}\\14^4\equiv13\pmod{17}\\14^8\equiv16\equiv-1\pmod{17}\\(14^8)^{32}\equiv(-1)^{32}\equiv1\pmod{17}$$The rest is $1$, ...
1
vote
1answer
114 views

Any 'odd unit fraction' whose denominator is not $1$ can be represented as the sum of three different 'odd unit fractions'?

Let us call a fraction whose denominator is odd 'odd fraction'. Also, let us call an odd fraction whose numerator is 1 'odd unit fraction'. Then, here is my question. Question : Is the following ...
1
vote
3answers
59 views

Congruences doubt!

What the rest of the division $2^{100}$ by $11$? $$2^5=32\equiv10\equiv-1\pmod{11}\\(2^5)^{20}=2^{100}\equiv-1^{20}\;\text{or}\; (-1)^{20}$$??
6
votes
1answer
155 views

Formal proof $\binom{n}{k}$ is an integer

In mathematics one defines: $\left(\begin{array}{c}n\\k\end{array}\right)=\displaystyle\frac{n!}{k!\cdot (n-k)!}$ This is the number of combinations of $k$ elements from a collection of $n$ ...
1
vote
2answers
133 views

Arithmetic Progressions containing integers close to a power of 2

Consider an arithmetic progression of the form $\{kq: k \in \mathbb{Z}\}$, where $q$ is an odd integer. Do such APs always contain a number of the form $2^n \pm 1$? I was initially interested in the ...
1
vote
1answer
58 views

Prove $k!(e-s_k)$ is irrational.

Given that $\frac{p}{q} = e = 1 + \frac{1}{1!} + \frac{1}{2!} + ... + \frac{1}{k!} + \frac{e^{z}}{(k+1)!}$ for some $z$ in $[0,1]$ (using Taylor's theorem), and that $s_k = 1 + \frac{1}{1!} + ...
2
votes
2answers
236 views

Number theory question

$K$ is a three digit number such that the ratio of the number to the sum of its digits is least. What is the difference between the hundreds and the tens digits of $K$ a) 9 b) 8 c) 7 d) ...
2
votes
4answers
172 views

Primitive root modulo $p=8t + 3$

Suppose that p is a prime of the form $8t +3$ and that $q=(p-1)/2$ is also a prime. Show that 2 is a primitive root modulo p. We must show that $ 2^{(p-1)} \equiv1 \ (mod \ p) $ for this we use ...
0
votes
1answer
63 views

will $x_{n+1}=x_n/2$ if $x_n$ is even; otherwise $x_{n+1}=3*x_n+1$, will $x_n$ shrink to 1?

I was asked this question that, for any $x_1 \in \mathbb{N}$, define the sequence as $$x_{n+1}=\left\{ \begin{array}{l l} x_n/2 & \quad \text{if } x \text{ is even} \\ 3 x_n+1 & ...
1
vote
1answer
143 views

Show that $HK=\mathbb{Z}_n^\times$

Let $p$ and $q$ be distinct prime numbers and $n=pq$. Show that $HK=\mathbb{Z}_n^\times$ for the subgroups $H=\{[x]\in\mathbb{Z}_n^\times\mid x\equiv 1\pmod{p}\}$ and $K=\{[y]\in\mathbb Z_n^\times ...
1
vote
1answer
80 views

System of 3 congruences (linear and non-linear)

The problem asks to find all simultaneous solutions to the system of equations. $x^2 \equiv 1 \pmod 8$ $5x \equiv 15 \pmod {20}$ $5x \equiv 1 \pmod 6$ I really can't find any good examples of how ...
12
votes
4answers
748 views

Proof that $n^3 + 3n^2 + 2n$ is a multiple of $3$.

I'm struggling with this problem: For any natural number $n$, prove that $n^3 + 3n^2 + 2n$ is a multiple of $3$. That $n^3 + 3n^2 + 2n$ is a multiple of $3$ means that: $n^3 + 3n^2 + 2n = 3 ...
2
votes
2answers
79 views

How to find $p$ and $q$ if we have $\operatorname{lcm}(p,q)=b$ and $p+q=a$ where ($a,b \in \mathbb{N}$) and $p>q$.

What is the general formula to find $p$ and $q$ if we have $\def\lcm{\operatorname{lcm}}\lcm (p,q)=b$ or $\gcd(p,q)$ and $p+q=a$ where ($a,b \in \mathbb N$) and $p>q$? Example: $\lcm(p,q)=84$ and ...
0
votes
1answer
69 views

Pythagorean triples generation Euclid's proof

How can I show that $a,\,b,\,c$ have no common divisor where $a = s\cdot t,\,b = \frac{(s^2 -t^2)}{2},\,c = \frac{(s^2 + t^2)}{2}$ and $s,\,t$ are both odd and they are relatively prime? Does anybody ...
2
votes
2answers
73 views

Does $ x^p+y^p=kz^p$ have any solutions when $x,y,z,k,p>2, gdc(x,y,z)=1$?

Does the Diophantine equation $$\displaystyle x^p+y^p=k(z^p)$$ have any solutions when $x,y,z,k,p>2, $ and $ x,y,z$ are co-primes?
2
votes
2answers
73 views

Proof that $q^2$ is indivisible by 3 if $q$ is indivisible by 3.

Let $q$ be a natural number. Show that if $q$ is not divisible by $3$, the neither is $q^2.$ Is this proved by contradiction or a different method of proof? All responses are appreciated...
4
votes
1answer
796 views

What is the use of the Chinese Remainder Theorem

What is the most tangible way to introduce the Chinese Remainder Theorem? What are the practical and really interesting examples of this theorem. I am looking for examples which have a real impact on ...
1
vote
2answers
56 views

If both the sum and sum of squares of two rationals are integers, the two rationals are integers too

There are two rational numbers $\alpha, \beta$ such that $\alpha + \beta,\ \alpha^2 + \beta^2$ are both integers. Prove that $\alpha, \beta$ are integers. I started off by assuming that $\alpha = ...
8
votes
3answers
197 views

centenes of $7^{999999}$

What is the value of the hundreds digit of the number $7^{999999}$? Equivalent to finding the value of $a$ for the congruence $$7^{999999}\equiv a\pmod{1000}$$
2
votes
0answers
522 views

Liouville function and perfect square

Let $n \in \mathbb{Z}$ with $n > 0$. Let $F(n) = \sum_{d \mid n} \lambda(d)$. Prove that $$F(n) = \begin{cases}1, \quad \text{if }n \text{is a perfect square}\\ 0, \quad \text{otherwise} ...
1
vote
3answers
50 views

Demonstration congruences

Assuming that $m=p_1^{\alpha_1}...p_r^{\alpha_r}$. Show that $$a\equiv b\pmod m\Longleftrightarrow a\equiv b\pmod {p_i^{\alpha_i}},\;i={1,...,r}$$ I always thought very beautiful statements that ...
5
votes
1answer
89 views

Is the infinite continued fraction $[0;0,0,\ldots]=0$?

Wolfram|Alpha states that the infinite continued fraction $$\cfrac{1}{0+\cfrac{1}{0+\cdots}}=0.$$ Assuming $[0;0,0,\ldots]$ exists implies that the continued fraction is $1$, since ...