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

learn more… | top users | synonyms (1)

1
vote
2answers
243 views

Which of the following sets is a complete set of representatives modulo 7?

Which of the following sets is a complete set of representatives modulo 7? 1) (1, 8, 27, 64, 125, 216, 343) 1 mod 7 = 1 8 mod 7 = 1 27 mod 7 = 6 64 mod 7 = 1 125 mod 7 = 6 216 mod = 6 343 mod ...
2
votes
0answers
144 views

proving $n$-ary associativity/commutivity of multiplication

EDIT: I tried to do the induction myself... looks pretty solid to me, what do you guys think? Basis: $a\cdot b\cdot c$ Show all possible cases for 3 terms (using commutivity and associativity) and ...
3
votes
2answers
188 views

Proof using the Principle of Mathematical Induction

Use induction to prove that $n! > 3n$ for $n\ge4 $. I have done the base case and got both sides being equal to $24>12$ for $n=4$. However, when doing the inductive step I can't seem to ...
4
votes
1answer
80 views

On the period of the decimal representation of $n$ when $\gcd(n, 10) \neq 1$

Suppose that $n = 2^a5^bm$, where $n > m > 1$ are integers, with $\gcd(m, 10) = 1$, and $a, b$ are non-negative integers. How does one show that the lengths of the periods of the decimal ...
0
votes
1answer
69 views

Math Help on Number theory

I suddenly thought of this conjecture. I'm not sure if it's true: " Let m be a positive integer such that m= $p_{\it 1}^{i_1}$ $p_{\it 2}^{i_2}$... $p_{\it k}^{i_k}$ where $p_1$,...,$p_k$ are ...
1
vote
2answers
1k views

Are there any real life applications of the greatest common divisor of two or more integers?

I am looking for real life applications of gcd. I have found one with tiles but there must be many more of these type.
1
vote
3answers
881 views

Carmichael proof of at least 3 factors

I'm having some trouble while trying to prove the well known fact that a Carmichael number has at least 3 prime factors. Basically, how I see it, I have 2 options: building a number b that will ...
1
vote
2answers
78 views

Irreducible in $2{\bf N}$ divides product of terms doesn't imply it divides a term

Lemma $3$. if $p$ is prime and $p$ divides $bc$, then $p$ divides $b$ or $p$ divides $c$. proof: we use corollary $8$ an application of Bezout's identity, namely: if $a$ divides $bc$ and $(a,b)=1$, ...
0
votes
3answers
220 views

If $x^2+ax+b=0$ has a rational root, show that it is in fact an integer

I have tried as follows. Please help to double check the proof! Thank you! Since $x=p/q$ ($p$, $q$ are integers), $(p/q)^2+(p/q)a+b=0$ So, $(p/q)^2=-b-a(p/q)$ then, $p^2=-bq^2-a(p/q)q^2$ and, $p = ...
0
votes
4answers
83 views

Show that $5^n + 6^n = 0 \pmod{11}$ for all odd $n$

show that $5^n + 6^n = 0 \pmod{11}$ for all odd number $n$, but not for any even number $n$. I was not sure about this question. Do I have to pick numbers for $n$? Until I get odd number?
0
votes
2answers
86 views

Show that the smallest $k > 0$ such that $a$ divides $bk$ is $k = [a,b]/b$.

How do I show that the smallest $k > 0$ such that $a$ divides $bk$ is $k = [a,b]/b$ where $[a,b]$ is the least common multiple of $a$ and $b$? I tried looking under "unique factorization" but ...
1
vote
1answer
592 views

Prove that if a number $n > 1$ is not prime, then it has a prime factor $\le \sqrt{n}$.

Prove that if a number $n > 1$ is not prime, then it has a prime factor $\le \sqrt{n}$. My answer is that this is not always true, because you can pick a non-prime number that is greater than $1$ ...
0
votes
2answers
50 views

Show that $[a, m] = m$ if and only if $a$ divides $m$, where $[a, m] = \mathrm{lcm}(a,m)$

Show that $[a, m] = m$ if and only if $a$ divides $m$, where $[a, m] = \mathrm{lcm}(a,m)$
0
votes
2answers
86 views

Proof that from FTA follows $n>\alpha_{n,k}$

Recall the FTA in canonical form $$n=p_1^{\alpha_{n,1}}p_2^{\alpha_{n,2}} \cdots p_k^{\alpha_{n,k}} = \prod_{i=1}^{k}p_i^{\alpha_{n,i}}$$ where $n,i,k \in\Bbb N$ and $\alpha \in\Bbb N_0$. Two ...
9
votes
1answer
753 views

Special cases of the Stark-Heegner theorem with simple proofs

The Stark-Heegner theorem states that the ring of integers of the quadratic number field $\mathbb Q(\sqrt{m})$, where $m$ is a squarefree negative integer, is a principal ideal domain, iff ...
1
vote
1answer
113 views

How to teach the division algorithm?

What is the best way to introduce the division algorithm? Are there real life examples of an application of this algorithm. At present I state and prove the division algorithm and then do some ...
24
votes
1answer
337 views

The final number after $999$ operations.

I wanted to know, let the numbers $1,\frac12,\frac13,\dots,\frac1{1000}$ be written on a blackboard. One may delete two arbitrary numbers $a$ and $b$ and write $a+b+ab$ instead. After $999$ such ...
10
votes
2answers
187 views

Prove that for any integer $n$, the fraction $\frac{3n+2}{4n+3}$ is reduced.

I need help with this question. Prove that for any integer $n$, the fraction $\frac{3n+2}{4n+3}$ is reduced.
2
votes
2answers
103 views

Simple (easy to understand) definition of squarefree integers.

I am first year Calculus student and have been reading a little bit about some basic number theory topics and I cannot seem to find square-free numbers to be defined in simple symbolic notation, ie. ...
1
vote
2answers
68 views

Is the quotients of a group of triangular distributed numbers still following a triangular distribution?

I have a group of numbers (about 10000 numbers) between 0.8 and 1.0 which follows simple triangular distribution (for example, lower limit: 0.8, upper limit: 1.0, mode: 0.9). If I divide 2 by each ...
1
vote
1answer
66 views

How $\log p$ distributed?

From literature we know: If a number $n \le x$ is chosen at random, and choose $\lambda \ge 0$ and $j$ not too large (say $\lambda ,j \le 20$) then the number of primes in $[ n , n + \log(n) ]$ is ...
7
votes
2answers
3k views

Is there any mathematical theory behind sudoku?

In particular I would like to know: is it possible to say if a sudoku is solvable only having the initial scheme? If yes, what are the condition for which it is solvable? Given the initial scheme of ...
2
votes
4answers
779 views

If $w^2 + x^2 + y^2 = z^2$, then $z$ is even if and only if $w$, $x$, and $y$ are even

I'm trying to go through the MIT opencourseware Mathematics for Computer Science (6.042J). I've been stumped for half a day trying to figure it out. Something isn't clicking, and I could use some ...
4
votes
6answers
368 views

Show that $7 \mid( 1^{47} +2^{47}+3^{47}+4^{47}+5^{47}+6^{47})$

I am solving this one using the fermat's little theorem but I got stuck up with some manipulations and there is no way I could tell that the residue of the sum of each term is still divisible by $7$. ...
2
votes
1answer
57 views

number theory equation involving GCD

Fix the natural number $b$. How can I solve ? $$ x+\gcd(x,b) \equiv 0 \mod(b) $$ Can anyone please give me a reference? Best
2
votes
3answers
46 views

Help with a step in rearranging this problem

i'm working through the proof of this theorem; If $x$ is any real number other than $1$, then $$\sum_{j = 0}^{n -1} x^j = 1 + x + x^2 + \cdots + x^{n-1} = \frac{x^n-1}{x-1}$$ But i'm struggling with ...
1
vote
1answer
67 views

Numbers in a circle: how many sets of consecutive numbers have positive sum?

One hundred integers are written around a circle, and it is known that their sum is $1$. We will call a subset of several successive numbers a "chain". Find the number of chains whose members have ...
2
votes
1answer
66 views

Divisibility by Quadratics

The natural numbers $a$ and $b$ are such $a^2+ab+1$ is divisible by $b^2+ba+1$. Prove that $a = b$. I tried to algebraically manipulate it as follows: $(b^2 + ba + 1)k = a^2 + ab + 1$ $[b(a + ...
2
votes
3answers
417 views

Congruence classes: Find the inverse

I have the following problem: If $ [3640]$ is invertible in $\mathbb {Z}_{7297}$ then determine its inverse. Okay. The first thing I thought was: $$3640x\equiv 1 \pmod{7297}$$ But isn't there ...
2
votes
2answers
65 views

Number of solutions in a finite field

let $F$ be a field of $p^b$ elements, $p$ prime and $b \in \mathbb{N}$. Suppose I have $(a_1, a_2, \ldots, a_s) \in F^s$ and an equation $$ 0 = a_1 x_1 + \dots + a_s x_s. $$ I was wondering if anybody ...
0
votes
2answers
56 views

Explanation of $\equiv$, and which of these statements involving it are true?

I am not familiar with this three lines equal sign and reading about it didnt really help with the original problem, which is: From the options below choose up to two that show correct solutions ...
1
vote
2answers
100 views

Show that $\sum\limits_{p \leq x} \frac{1}{p}$ ~ ${\log\log{x}}$ when ${x \to \infty}$ (here p is a prime)

I saw that some of you were upset over my last question, so I decided to ask a more interesting question: Show that $\sum\limits_{p \leq x} \frac{1}{p}$ ~ ${\log\log{x}}$ when ${x \to \infty}$ (here ...
2
votes
0answers
60 views

Number of decimal places to be considered in division

This must be a basic question. But i need some help. What is the number of decimal places that needs to be considered normally in division operations in order to represent the dividend value as a ...
1
vote
2answers
68 views

Calculate the limit $\lim_{x \to \infty} \ \frac{1}{2}\sum\limits_{p \leq x} p \log{p}$ (here p is a prime)

Calculate the limit $\lim_{x \to \infty} \ \frac{1}{2}\sum\limits_{p \leq x} p \log{p}$ (here the sum goes over all the primes less than or equal to x) using the Prime Number Theorem. I think I've ...
2
votes
0answers
184 views

Looking for proof-without-words of Bezout's identity

I'm looking for a "proof-without-words" of Bezout's identity (for integers). Does anyone know of one?
1
vote
3answers
420 views

The smallest positive integer in the set $\{24u+60v+200w : u,v,w \in \Bbb Z\}$is given by which of the following number?

I am stuck on the following problem: The smallest positive integer in the set $\{24u+60v+200w : u,v,w \in \Bbb Z\}$is given by which of the following number? The options are: ...
0
votes
5answers
93 views

Help me get the Divisor

I want to divide a particular number with $4,7,$ and $13$, but I want to get the remainder as $1,2$ and $4$ accordingly. Could you please help me get the number (If feasible at all) and please explain ...
6
votes
3answers
185 views

$(4k-1)^2 +(4k)^2$ is a perfect square

Let $k$ be strictly bigger than 1. Is there any integer k such that $(4k-1)^2+(4k)^2$ is a perfect square? My computation shows that there are infinitely many such $k$, namely those arising from the ...
0
votes
2answers
48 views

Translation of; If X is any real number other than 1, then…

i've just started reading a book on number theory and am trying to follow along with the example proofs of theorems. I've not had too much trouble once I have managed to "translate" the mathematical ...
1
vote
2answers
251 views

Determining the smallest possible value

If both $11^2$ and $3^3$ are factors of the number $a \times 4^3 \times 6^2 \times 13^{11}$, then what is the smallest possible value of a? IS there any trick to answer this type question quickly? ...
9
votes
2answers
182 views

Polynomials mapping factorials to factorials

I'm looking for all polynomials $P(x)$ with integer coefficients such that for every $n \in \Bbb N$ there is an $m \in \Bbb N$ such that $P(n!)=m$!. The only solutions seem to be the constant ...
1
vote
1answer
68 views

Polynomial whose only values are squares

Given a polynomial $ P \in \Bbb Z [X] $ such that, $ P (x)$ is the square of an integer for all integers x, is $ P $ necessarily of the form $ P (x)= Q (x)^2$ with $ Q \in \Bbb Z [X]$?
6
votes
2answers
182 views

Prove that $(3+5\sqrt{2})^m=(5+3 \sqrt{2})^n$ has no positive integer solutions?

Is my proof ok? I set $b=3+5 \sqrt{2}$, so that we have $b^m=(b+2-3 \sqrt{2})^n$ , or $b^m=(b+\sqrt2(\sqrt2- 3))^n$. Since $RHS<LHS$, $n>m$ . However, from what we know about binomial ...
1
vote
2answers
36 views

Question about modular arithmetic and divisibility

If $$a^3+b^3+c^3=0\pmod 7$$ Calculate the residue after dividing $abc$ with $7$ My first ideas here was trying the 7 possible remainders and then elevate to the third power $$a+b+c=x \pmod 7$$ ...
0
votes
1answer
67 views

The sum of consecutive digits

a) Find the natural numbers ${\overline{ab}}$ such that ${\overline{ab}}= a+(a+1)+...+b$. b) Exist natural numbers ${\overline{abc}}$ such that ${\overline{abc}} = a+(a+1)+...+{\overline{bc}}?$; ...
1
vote
0answers
33 views

A Greatest Common Divisor Property [duplicate]

Show that: If $c|a^m-1$ and $c|a^n-1$ then $c|a^{gcd(m,n)}-1$
5
votes
2answers
374 views

On the number of quadratic residues $\pmod{pq}$ where$p$ and $q$ are odd primes.

I have read that the formula for the number of quadratic residues $\pmod{pq}$ for odd primes $p$ and $q$ is $\frac{(p-1)(q-1)}{4}$. Is this the case, and if it is, why is it the case and how would one ...
0
votes
1answer
450 views

Questions based on the greatest integer and fractional part functions

If $\displaystyle x = \left[\frac{3^{31}+2^{31}}{3^{29}+2^{29}}\right]$, then $x = $ If $x\left[x\left[x \left[x\right]\right]\right] = 2013$, then $x = $ If $\{x^2\}+\{x\} = 1$, then $x = $ My ...
2
votes
1answer
76 views

Why inverse modulo exponentiation is harder than inverse exponentiation without modulo

I am new to number theory. I read in cryptography inverse modulo exponentiation is used because it is hard. But I couldn't understand the advantage of it over inverse exponentiation without modulo. ...
-4
votes
3answers
478 views

why can't we divide by zero ?! [duplicate]

in arabic sites which is interested in maths , i find many topics like ,here is a proof that 0=2 . and we answer that the proof is wrong as we can't divide by zero . but i really wonder , why ...