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

learn more… | top users | synonyms (1)

1
vote
1answer
52 views

Properties of Digit root

Why the digit root of any number calculated in any way remains same...e.g Let $f(x)$denote the digit root of $x$ $f(1237)=f(12+37)=f(49)=f(123+7)=f(130)=4$ I checked numerically with many numbers ...
14
votes
4answers
779 views

“If $1/a + 1/b = 1 /c$ where $a, b, c$ are positive integers with no common factor, $(a + b)$ is the square of an integer”

If $1/a + 1/b = 1 /c$ where $a, b, c$ are positive integers with no common factor, $(a + b)$ is the square of an integer. I found this question in RMO 1992 paper ! Can anyone help me to prove ...
0
votes
1answer
61 views

Find all $(a,b,c)\in\mathbb{Z}^3$ such that $b^2-4ac=-20$, and $-|a|<b\le|a|<|c|$, or $0\le b\le|a|=|c|$.

Find all $(a,b,c)\in\mathbb{Z}^3$ such that $b^2-4ac=-20$, and either of the following is true: $-|a|<b\le|a|<|c|$, or $0\le b\le|a|=|c|$. We see that if $(a,b,c)$ is a solution, then so is ...
0
votes
1answer
942 views

Step in proof: Sum of euler phi function over divisors (Group Theory)

Proof: $$\sum_{d|N}\phi(d)=N$$ where the sum is over $d\in div(N)$ Let $G$ be the cyclic group $\mathbb Z/N \mathbb Z$. Then $$N = \sum_{g \in G} 1 = \sum_{d|N}\sum_{g \in G, ord(g)=d} ...
5
votes
1answer
106 views

If $\sqrt[3]{a} + \sqrt[3]{b}$ is rational then prove $\sqrt[3]{a}$ and $\sqrt[3]{b}$ are rational

Assume there exist some rationals $a, b$ such that $\sqrt[3]{a}, \sqrt[3]{b}$ are irrationals, but: $$\sqrt[3]{a} + \sqrt[3]{b} = \frac{m}{n}$$ for some integers $m, n$ $$\implies \left(\sqrt[3]{a} ...
2
votes
1answer
121 views

Is it true that $p_{n}+p_{n+1}>p_{n+2}$ for all $n\geq 2\ ?$

Let $p_{n}$ denotes the $n$-th prime number. Is it true that $p_{n}+p_{n+1}>p_{n+2}$ for all $n\geq 2\ ?$
1
vote
6answers
145 views

Euclidean Algorithm Question

So I have been asked to find $d=(a,b)$ when $a=1109$ and $b=4999$ and express $d$ as a linear combination of $a$ and $b$ Well I have worked out that $d=1$ but I am struggling to express $d$ as a ...
0
votes
1answer
61 views

Prove $n^3+3n$ is even in case $n=2a+1$

Prove that $\forall n \in Z$, $n^3+3n$ is even. Attempt: I am solving this problem using proof by cases. Case 1 is when $n$ is even, i.e. $n=2b$. This one is easy. However, in case 2 when $n$ is ...
8
votes
1answer
296 views

Are differences between powers of 2 equal to differences between powers of 3 infinitely often?

Consider the equation $2^a-2^b=3^c-3^d$ where $a>b>0$, $c>d>0$, and $a,b,c,d$ are all integers. A computer search for solutions with $a,c\le20$ only finds 8-2=9-3, 32-8=27-3, and ...
1
vote
1answer
228 views

How many non-zero quadratic residues are there for $p^k$, where $p$ is an odd prime and $k$ a positive integer?

How many non-zero quadratic residues are there for $p^k$, where $p$ is an odd prime and $k$ a positive integer? Hi everyone, just need a bit of help for this practice question, I have proved that for ...
4
votes
1answer
69 views

How to reason about congruences? If $x^2 \equiv a$ (mod $m$) and $y^3 \equiv a$ (mod $m$), then $\gcd(a,m) = 1$

Generally, I have no high level conception of what is going on in my number theory class. It feels like a loose collection of theorems and techniques that you can use on some problems, but I have ...
9
votes
1answer
161 views

Does there exist an infinite set of integers such that the geometric mean of any of its subsets is an integer?

Is there an infinite set $S$ such that for any subset with $m$ integers the geometric mean is also an integer? We can always find a set, $S_n$ with $n$ elements which satisfies the given requirement: ...
0
votes
1answer
97 views

$ 1^k + 2^k + \cdots + (p-1)^k \equiv \begin{cases} -1 \mod p, \text{ if } p-1 | k, \\ 0 \mod p, \text{ if } p-1 \not | k. \end{cases}$ [duplicate]

If $p-1 | k \Rightarrow k = (p-1) n$, for some $n \in \mathbb{N}$. Then we $ 1^{(p-1)^n} + 2 ^{(p-1)^n} + \cdots + (p-1)^{(p-1)^n} = \underbrace{1 + 1 + \cdots + 1}_{p-1} = p-1 \equiv -1 \mod p.$ The ...
4
votes
2answers
1k views

Prove that in a sequence of numbers 49 , 4489 , 444889 , 44448889…

Prove that in a sequence of numbers 49 , 4489 , 444889 , 44448889... in which every number is made by inserting 48 in the middle of previous as indicated, each number is the square of an integer.
4
votes
3answers
144 views

If prime $p\not \equiv 1 \pmod 3$, then $p^2 = a^2 + ab + b^2$ has no solutions $a,\,b \in \mathbb{N} \}$

I would like to stress that this is a homework question that is worth a significant amount of my grade, so don't blurt out a solution if you find it. I am trying to show that if $p^2 \in S := \{a^2 + ...
0
votes
2answers
38 views

Number theory problem on numbers II

is n/m , n>m rational number? like 7/2? I want to know 7/2 is rational number or not if it is not why and if it is why?
0
votes
1answer
89 views

Simple divisibility problem in elementary number theory

Find all positive integers $n$ such that $n+2009$ divides $n^2+2009$ and $n+2010$ divides $n^2+2010$. I'm kind of new in number theory and got stuck in this simple problem. I'm almost sure that the ...
0
votes
1answer
41 views

Show that $x$ is square free iff for any $y,z$ positive integers $x=yz \Rightarrow \mathrm{hcf}(y,z) = 1$

Show that x is square free if and only if $$x = yz\Rightarrow\mathrm{hcf}(y,z) = 1$$ where x and y are positive integers. I have tried using coprime factorisation leading to $$1 = jy + kz$$ But ...
1
vote
1answer
90 views

How to write the proof for this?

Let $a,b,c \in \mathbb{Z}$, and $a \neq 0$. Use a proof by contradiction to show that if $(a \nmid (bc))$ then $(a \nmid b)$. The symbol $\nmid$ stands for "does not divide". I got the layout, but I ...
3
votes
3answers
94 views

why check all primes under the root of an interger?

I am in high school and I need to factorize numbers. My teacher told me to check all numbers which are smaller than the root of the number I want to factorize. This seems to work just fine, but I do ...
6
votes
5answers
402 views

How can I prove by induction that $9^k - 5^k$ is divisible by 4?

Recently had this on a discrete math test, which sadly I think I failed. But the question asked: Prove that $9^k - 5^k$ is divisible by $4$. Using the only approach I learned in the class, I ...
2
votes
2answers
415 views

Two polynomials $r_1, r_2 \in R[X]$ are equal if and only if the cofficients $a_i, b_i$ are equal for all $i, 0 \leq i \leq n$ - Purely a definition?

I've read that two polynomials $r_1, r_2 \in R[X]$ on the form $r = a_nX^n + ... + a_1X + a_0$ are equal if and only if the cofficients of $r_1, r_2$: $a_i, b_i$ are equal for all $i, 0 \leq i \leq ...
2
votes
2answers
202 views

What is the smallest integer $n$ greater than $1$ such that the root mean square of the first $n$ integers is an integer?

What is the smallest integer $n$ greater than $1$ such that the root mean square of the first $n$ integers is an integer? The root mean square is defined as: $$\sqrt{\left(\frac{a_1^2 + a_2^2 + ...
0
votes
2answers
57 views

Is the proof of the claim correct? Is the claim true?

We say that an integer a is divisible by the nonzero integer b, if a = bc for some integer c: When a is divisible by b, we write b | a and say b divides a. Claim: Let a and b be nonzero integers. If ...
1
vote
1answer
53 views

Proof that for $e>3$, the number of quadratic residues $a$, s.t. $gcd(a,2^e)$ and $0<a<n $ is $2^{e-3}$

I'm just wondering if someone can help with the 2nd part of the proof to understand this proposition leading to the conclusion. I understand that for $2^e, e>3$, $a$ is a quadratic residue, if and ...
0
votes
2answers
43 views

product of two numbers ending in 6 also ends with

We have to proove that "the product of two numbers ending in 6 also ends with 6" mathematically. I have no clue how to start. I don't want you to proove it for me! but some hints would be very ...
-1
votes
2answers
270 views

Show that if $10$ divides into $n^2$ evenly then $10$ divides into $n$ evenly

I'm not sure how to show that if $10$ divides into $n^2$ evenly, then $10$ divides into $n$ evenly.
0
votes
1answer
76 views

Divisibility of a number by $(4k+3)$ in minimum time

Please suggest any algorithm with minimum time complexity to check whether a number $n$ is divisible by at least one $(4k+3)$ where $k>0$ is integer and $(4k+3)\le n$?
6
votes
2answers
526 views

Prove that $\phi(n) \geq \sqrt{n}/2$

So I'm trying to prove the following two inequalities: $$\frac{\sqrt{n}}{2} \leq \phi(n) \leq n.$$ The upper bound we get from simply noting that $\phi(n) = n \prod_{p | n}\left( 1 - ...
1
vote
1answer
146 views

Quadratic Reciprocity - Legendre Symbols

Find the value of $((1\cdot 2)/73)+((2\cdot 3)/73)+...+((71\cdot 72)/73)$. This is based off each fraction being a Legendre Symbol. I tried to find a pattern... but I could't find anything. Also, I ...
1
vote
1answer
73 views

A small application of Fermat's Little Theorem

Suppose that $q$ is some prime number distinct from prime $p$ (in particular, assume $q < p$). I would like to show that the elements $q^1, q^2, ... , q^{p-1}$ modulo $p$ are all distinct from each ...
6
votes
1answer
688 views

Why can't this number be written as a sum of three squares of rationals?

This may be a very naive question and I apologize in advance. Suppose that $n$ is a positive integer which cannot be written as a sum of three squares $a^2+b^2+c^2$ for integers $a,b,c\in\mathbb{Z}$. ...
10
votes
0answers
332 views

A question about the divisibility of sum of 2 consecutive primes.

Well as I was curious about the sum of $2$ consecutive primes, after proving that the sum for the odd primes always has at least 3 prime divisors, I came up with this question: Find the least ...
1
vote
2answers
69 views

Proof the quotient and remainder exists in $\mathbb{Z}^+$.

If $a$ and $b$ are positive integers, prove that there exists an integer $q$ called the quotient and an integer $r$ called the remainder such that $a = q b + r$ and $0 \leq r < b$. I've seen ...
2
votes
6answers
140 views

Prove that $6$ divides $n(n + 1)(n + 2)$

I am stuck on this problem, and was wondering if anyone could help me out with this. The question is as follows: Let $n$ be an integer such that $n ≥ 1$. Prove that $6$ divides $n(n + 1)(n + 2)$. ...
2
votes
1answer
259 views

cryptology beginner book

I am taking a number theory course this semester which includes a brief intro to the field of cryptology including only : Applications to Cryptology, Character Ciphers,Block and stream ...
0
votes
1answer
323 views

Uniqueness Proof for Division Algorithm using Contradiction

Let $a, b, \mathbb \in \mathbb {Z}$ and let there exist integers $q, q_1, r, r_1$ such that the two pairs $(q,r)$ and $(q_1,r_1)$ satisfy the properties: $$\ \ \ \ a = qb+r \quad \ \ \ \ \ \ \ ; 0 ...
2
votes
1answer
142 views

Question In Elementary Number Thoery

In the book, "Elementary Number Theory 6th Edition(David M. Burton)", I don't know how to solve this problem. P.58 number 18 (a) If p is a prime and b is not divisible by p, prove that in the ...
1
vote
1answer
43 views

Specific Annual Examination Marks

Steve has recently got his annual exam result.He has got upper than 690 out of 750.His obtained marks has odd number of factors.What is his obtained marks?
0
votes
3answers
45 views

How to make every integer out of $5k + 8q$?

Expression given: $N = 5k + 8q$ ($k$ , $q$ integer). Prove that we can make any integer from this expression. For example: $0= 5\cdot0+8\cdot0$; $5 = 5\cdot1+8\cdot0$; $3 = 8\cdot1 +5 ...
5
votes
1answer
101 views

Show that $\sum_{d \mid n} \frac{\phi_k(d)}{d^k}=\frac{1^k +2^k + \cdots + n^k}{n^k}$

I'm considering the following fun problem in number theory: Let $n \in \mathbb{Z}$ with $n > 0$. If $k$ is a nonnegative integer, then $$\phi_k(n) = \sum_{1 \leq d \leq n, \, (d,n)=1} d^k.$$ Let ...
0
votes
1answer
74 views

For any $a \in \mathbb R$ and any $n \in \mathbb N^+$ there exists $q \in \mathbb Q$ such that $|a-q|< \frac{1}{n}$.

For any $a \in \mathbb R$ and any $n \in \mathbb N^+$ there exists $q \in \mathbb Q$ such that $|a-q|< \frac{1}{n}$. I think i can prove this is false, let $a=2,n=2,q=1/2$ so $|2-\frac{1}{2}|< ...
0
votes
1answer
152 views

Number Theory about least common multiple

Let a and b be positive integers and let [a,b] denote the least common multiple of a and b. Show that there exist integers x and y such that $$ \left(\frac xa\right) + \left(\frac yb\right) = ...
17
votes
5answers
4k views

Fermat's Last Theorem near misses?

I've recently seen a video of Numberphille channel on Youtube about Fermat's Last Theorem. It talks about how there is a given "solution" for the Fermat's Last Theorem for $n>2$ in the animated ...
1
vote
1answer
41 views

sequence of sets with $\limsup A_n = \mathbb N$

Find a sequence of one-point-sets $A_n = \{\ell_n\}$ with $\ell_n\in\mathbb N$ for all $n\in\mathbb N$, such that $$\limsup_{n\to\infty} A_n=\mathbb N$$ I know the definition of the $\limsup$ of a ...
4
votes
2answers
306 views

Exponent of Prime in a Factorial [duplicate]

I was just trying to work out the exponent for $7$ in the number $343!$. I think the right technique is $$\frac{343}{7}+\frac{343}{7^2}+\frac{343}{7^3}=57.$$ If this is right, can the technique be ...
2
votes
2answers
632 views

Prove that $x^3 \equiv x \bmod 6$ for all integers $x$

Prove that $x^3 \equiv x \bmod 6$ for all integers $x$ I think I got it, but is this proof correct? We can write any integer x in the form: $x = 6k, x = 6k + 1, x = 6k + 2, x = 6k + 3, x = 6k + ...
1
vote
1answer
36 views

Solve $r=(p-1)+pr_1+p^2r_2$ for $r_1$ and $r_2$ when $r(p-1) \equiv 1$ (mod $p^3$)

Let $p$ be an odd prime. $\mathbb Z_{p^3}=\left\{0,1,...,p^3-1\right\}$ 1) Let $r$ be an element of $\mathbb Z_{p^3}$. Then, we can define $r$ as follows: $r=(p-1)+pr_1+p^2r_2$ for some $0\leq ...
1
vote
2answers
178 views

Find the units digit in the number $7^{9999}$.

I have step by step instructions from a previous example to follow, so I figure I know how to get the answer, but I don't understand fully why it works the way it does... By Euler's theorem, if ...
3
votes
1answer
312 views

Upperbound approximation to the sum of Euler's totient function

I am currently working on a solution to a problem related to the density of finite coprime sets. I believe that I have found a solution to this problem - though it can only be expressed in terms of ...