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

learn more… | top users | synonyms (1)

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
393 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
398 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
192 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
42 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
268 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
505 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
144 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
669 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
328 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 ...
0
votes
1answer
61 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
138 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
254 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
314 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
141 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
73 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
150 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
295 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
627 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
170 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
307 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 ...
0
votes
2answers
90 views

Problem with sum of factors.

The sum of the total number of factors of $999000$, $816480$ and $819529$ is $n$. How many ways can $n$ be written as $\sqrt{a}+b$ where $b$ is a non-negative positive integer?
2
votes
5answers
795 views

Suppose that $5\leq q\leq p$ are both prime. Prove that $24|(p^2-q^2)$. [duplicate]

Suppose that $5\leq q\leq p$ are both prime. Prove that $24|(p^2-q^2)$. This is what I got so far. I figured that since $p,q$ are bigger than $5$, there are only odd primes for this conjecture. ...
0
votes
1answer
421 views

Why perfect square has odd number of factors

can someone please describe me why only the perfect square has odd number of factors.why does other number not has odd numbers of factors? I understand it but don't find any mathmetical proof.Please ...
0
votes
1answer
30 views

Let $a,b,z_1,z_2 \in \mathbb{Z}$ with $a>0$ and $z_1-z_2=a-1$. Prove that there is a unique $r$ and $q$ with $b=aq+r$ and $z_1≤r≤z_2$.

Let $a,b,z_1,z_2 \in \mathbb{Z}$ with $a>0$ and $z_2-z_1=a-1$. Prove that there is a unique $r$ and $q$ with $b=aq+r$ and $z_1≤r≤z_2$. Please help! How do I prove $z_1≤r≤z_2$,and $S$ is not an ...
0
votes
1answer
158 views

Diophantine Equation: solving $x^2-y^2=45$ in integers

How should I solve $x^2-y^2=45$ in integers? I know $$(x+y)(x-y)=3^2\cdot 5,$$ which means $3\mid (x+y)$ or $3\mid (x-y)$, and analogously for $5$.
3
votes
1answer
789 views

Prove that there are infinitely many composite numbers of the form $10^n + 3$, $n=1,2,3…$

I'm doing some exam practice questions and I am totally stuck on this one, been racking my brain for days without much progress. I would truly appreciate some help. I tried so many different routes. ...
1
vote
3answers
123 views

√2+√3 is irrational

I’m trying to prove that $\sqrt{2}+\sqrt{3}+\ldots+\sqrt{n}$ is irrational. I have already proved that $\sqrt{2}+\sqrt{3}$ is irrational. Should I use a similar approach as below or is there a ...
1
vote
2answers
48 views

Show $a^2=6k+3 \Rightarrow a = 6n + 3$

Show that if $a^2=6k+3$, for some integer $k$, then also $a = 6n + 3$ for an integer n. Or in in other words: $a^2=6k+3 \Rightarrow a = 6n + 3$. Taking the square root, $a=\sqrt{6k+3}$, does not ...
1
vote
1answer
71 views

Induction on natural numbers

My textbook, Logic and Discrete Mathematics by Grassman and Tremblay, has an example which I can't wrap my head around (example 3.4; page 127). It shows that for all $n$, $2(n+2)\le(n+2)^2$. As the ...
11
votes
1answer
113 views

Is it true that $\left[\sqrt{n}+\sqrt{n+1}+\sqrt{n+2} \right ]=\left[\sqrt{9n+7}\right]$?

I know it's true that $$\left[\sqrt{n}+\sqrt{n+1} \right ]=\left[\sqrt{4n+1}\right],\forall n\in \mathbb N. \tag 1$$ Is it true that $$\left[\sqrt{n}+\sqrt{n+1}+\sqrt{n+2} \right ...
1
vote
1answer
58 views

How does one determine for which value of $z_0$ the equation $ax+by=z$ has positive integer solutions $(x,y)$ for all $z\geq z_0$?

I just recently learned about "Frobenius Numbers" from watching Numberphile on youtube (http://www.youtube.com/watch?v=vNTSugyS038) and they look strikingly like Diophantine equations in some sense... ...
2
votes
3answers
86 views

Number Theory equation

How can I prove $$288\mid 7^{2n+1}-48n-7$$ for all nonnegative integers $n$? My only thought was to write $$7^{2n+1}-7-48n=7(7^n+1)(7^n-1)-48n.$$ This didn't seem beneficial at all. Please help me ...
1
vote
3answers
90 views

Prove that any number of the form $a_3a_2a_1a_3a_2a_1$ is divisible by 91.

Prove that any number of the form $a_3a_2a_1a_3a_2a_1$ is divisible by 91. I got up to $a_3a_2a_1a_3a_2a_1$ = 1000001$a_3$ + 10010$a_2$ + 1100$a_1$. However none of the coefficients are divisible ...
2
votes
2answers
1k views

Solving Quartic Equation

Could someone please explain how to solve this : $x^4+3x^3-6x^2+16x+56=0$ - not the answer only, but a step-by-step solution.
3
votes
2answers
142 views

Prove Divisibility test for 11 [duplicate]

Prove Divisibility test for 11 "If you repeatedly subtract the ones digit and get 0, the number is divisible by 11" Example: 11825 -> 1182 - 5 = 1177 1177 -> 117 - 7 = 110 110 -> 11 - 0 = 11 11 ...
6
votes
0answers
117 views

What is the Gauss sum equivalent of $\Gamma(s+1) = s\Gamma(s)$?

Gauss sums are analogous to the Gamma function: fix a complex number $s$ with real part $>0$. Then we have a multiplicative character $\chi_s :\mathbf R^{\times}_{>0} \to \mathbf C^\times$ given ...
0
votes
1answer
65 views

What are the values of a and b such that $a^4 + 4 b^4$ is prime

What values of a and b will ensure $a^4 + 4 b^4$ is prime
0
votes
1answer
31 views

Proof: If $r \in R$ is irreducible then $ur$ is irreducible where $u$ is a unit.

If $r \in R$ is irreducible then $r=ab, a,b \in R$ implies $a$ or $b$ is a unit. How does one proof $ur$ is irreducible if $u$ is a unit. I must proof: $ur = mn, m, n\in R$ then $m$ or $n$ is a ...