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

learn more… | top users | synonyms

3
votes
1answer
24 views

For $d \in \mathbb{Z}$, if $d\mid a$ and $d\mid b$, show that $d\mid(a+b)$ and $d\mid(a-b)$.

Let $d > 0$ and $d \in \mathbb{Z}$. If $d$ divides $a$ and $d$ divides $b$ then I want to show that $d$ divides $a+b$ and $a-b$. If $d$ divides $a$ then there exist an $m$ such that $a = dm$. If ...
1
vote
4answers
65 views

Can someone calculate with modulo calculator this??

I need help calculating the following: $$146^{11} \pmod{12}$$ I think the answer is $8$, but I'm not sure. Can anyone help? Thank you very much.
-1
votes
1answer
30 views

Remainder of division [closed]

What is the remainder of the division of $10^{100}$ by $7$? What is the remainder of the division of $10^{100}$ by $13$? I have learnt Euler Theorem, and I think it will be useful for this ...
0
votes
2answers
27 views

Finding integer solution of congruence equation

Find all integer solution $x$ which are solutions to the following congruence relation: $243x+17=101$ (mod 725) In this question, I can only figure out 243 and 725 are relatively prime. But I ...
0
votes
0answers
38 views

Divisibility of a power sum by a prime

For a given prime $p>2$ and positive integer $k$, let $$S_k=1^k+2^k+...+(p-1)^k$$ We have to find the values of $k$ for which $p|S_k$. By the binomial theorem we know that $p|i^k+(p-i)^k$ when $k$ ...
3
votes
2answers
36 views

Calculating $2^{9999 }$ mod $100$ using Fermats little Theorem

By a modified version of the Fermat's little theorem we obtain that $a^{\phi(n)} \equiv 1$ mod $n$ whenever $(a,n)=1$. But my professor accidentally gave this question to calculate $2^{9999 }$ mod ...
0
votes
4answers
131 views

What does Pi equal to [duplicate]

What is the approximation of pi in a fraction form. I am very curious to know what it is. I have been seeing pi almost everywhere.
0
votes
1answer
17 views

Help finding the common factor of $q^{n-1}-p$ and $kq-p$

let $p,q$ be 2 non-zero coprime integers,$n\in\mathbb{Z}>1$ and $k$ any integer. For what $k$ do $q^{n-1}-p$ and $kq-p$ have a common factor? So far, I have been able to come up only with the ...
2
votes
0answers
56 views

Is this proof of a mathematical olympiad problem correct?

I'm quite sure about the exactness of my proof, but I'd like to hear (constructive) criticism about my writing. This is the problem: Every non-negative integer is coloured white or red, so that: 1) ...
1
vote
1answer
60 views

Diophantine Equation: $a^3=a(b^2+c^2+d^2)+2bcd$

Let $a,b,c,d\in \mathbb{Z}$. Solve $$a^3=a(b^2+c^2+d^2)+2bcd$$ I've tried everything but I haven't been able to find a general solution. Note: We may assume $\gcd(a,b,c,d)=1$ because of homogeneity. ...
2
votes
1answer
38 views

Checking the IBAN and dividing large numbers mod 97. Why does it work?

What's the reason (or is there an easy explanation) of why it is possible to calculate the division mod $97$ of a large number by first calculating it for the first $9$ (or $6$?) leftmost digits and ...
3
votes
3answers
38 views

Find all the positive integers $m$ such that $p_{m}≥2m$

Find all the positive integers $m$ such that $$p_{m}≥2m$$ where $(p_{m})$ is the sequence of prime numbers I have no idea to start.
-1
votes
1answer
45 views

Basic elementary number theory [duplicate]

I just enrolled in a class called "Elementary Number Theory" and I am left confused in every class due to the different notations and proofs shown. Is there a really basic book on Number Theory out ...
1
vote
4answers
67 views

when exactly does $711 \equiv \alpha \times 2015 \mod 1302$ have a solution?

I know this is quite a stupid question, but I just can't figure out whether or not $$711 \equiv \alpha \times 2015 \mod 1302$$ has a solution for $\alpha \in \mathbb{Z}$. In my eyes, 2015 and 1302 ...
0
votes
2answers
41 views

Find the digit using the given conditions [closed]

$N$ is a $50$ digit number (in the decimal notation). All the digits except the $26$th digit (from the left) are $1$. If $N$ is divisible by $13$, find the $26$th digit.
-1
votes
1answer
65 views

give direct proof of the fact $a^2 - 5a + 6$ is even for any integer [duplicate]

I know this is true but I don't know how to prove it. I have worked it out for the integers from $1$ to $10$ but this is not direct proof, is there a formula I need?
3
votes
2answers
175 views

A natural number $n>2$ is a prime iff $\prod_{k=1}^{n-1} k \equiv n-1 \pmod {\sum_{k=1}^{n-1} k}$

Is this proof acceptable ? Theorem 1 (Wilson). A natural number $n>1$ is a prime iff: $$(n-1)! \equiv -1 \pmod n.$$ Theorem 2. A natural number $n>2$ is a prime iff: ...
0
votes
3answers
61 views

Can someone calculate with modulo calculator? [closed]

Can someone show me how to calculate this one, Im having a little trouble. Thanks guys. $$123^{12}\equiv\;?\pmod{11}$$
2
votes
5answers
106 views

Testing integrality of a number

Let $x$ be a real number. Show that $x$ is an integer if and only if $$[x] + [2x] + \cdots + [nx] = n ([x] + [nx])/2,$$ for all natural numbers $n$. Can you give me an idea?
-1
votes
1answer
39 views

Division of natural numbers [duplicate]

How can I prove that $9|n$ if and only if $9$ divides the sum of the digits of $n$, where $n \in \mathbb{N}$
2
votes
1answer
19 views

solvability of $r^x \equiv a \pmod {n}$

$r^x \equiv a \pmod {n}$ Is it correct to say this congruence is solvable if and only if $\gcd(a,n) = 1$ ? I am looking for a proof or intuitive argument for making sense of this. Thanks in advance! ...
3
votes
6answers
64 views

Why Are There No Solutions To $2^x \equiv 3\pmod{9}$?

I know this congruence has no solutions because $\gcd(3,9) \ne 1$. I would like to understand why this gcd restriction is needed for solvability. Thanks!
3
votes
5answers
75 views

Show that if $a$ is an integer, then 3 divides $a^3 - a $

Show that if $a$ is an integer, then 3 divides $a^3 - a $ we can write, where $k$ is an integer; $a^3 - a = 3k $ $a(a^2 - 1) = 3k $ Now if $a = k$ then $a^2 -1 = 3$ and $a= \pm2 $ so $ a^3 - a = ...
2
votes
0answers
28 views

What is the meaning of this question?

Exercise: Consider the question of representing integers with the base a . In order to name the integers in this system we need words for the digits 0, 1, · · ·, a –1 and for the various powers of a: ...
4
votes
2answers
46 views

Prove that $89|2^{44}-1$

Is there any easier (less no. of steps or calculations) proof for this using congruences: $89|2^{44}-1$. My proof: $$2^6\equiv-25\mod89$$ $$2^5\equiv32\mod89$$ Now square both equations: ...
2
votes
1answer
32 views

Proving the existence of a bijection between $U_{mn}$ and $U_m \times U_n$ where $(m,n)=1$ , there by proving Euler $\phi$ is multiplicative

Without proving before hand that Euler's phi $(\phi)$ function is multiplicative , can we prove that there is a bijection between $U_{mn}$ and $U_m \times U_n$ , for any pair of relatively prime ...
2
votes
0answers
43 views

Prove there are no solutions to the equation $k(2^n-1)=(3^{2q+1}-1)$ where $n,q>1$.

Prove there are no solutions to the equation $k(2^n-1)=(3^{2q+1}-1)$ where $n,q>1$. For a start I reasoned that $n$ had to be odd as otherwise $3|2^n-1$ which was obviously bad. Furthermore, it ...
0
votes
1answer
30 views

Divisiblity of $n$ with $a,b,c$ is relative prime to p

Given an arbitrary prime $p > 2011$. Prove that there exist positive integers $a,b,c$ such that there exists some numbers from $a, b, c$ that are relatively prime to $p$, and for all positive ...
0
votes
2answers
48 views

If $\gcd (x,4) = 2$ and $\gcd(y,4) = 2$ then $\gcd(x+y,4) = 4$

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : If $(x, 4) = 2$ and $(y, 4) =2$, then $(x + y, 4) = 4$, where $(a,b)$ denotes the ...
2
votes
3answers
98 views

Prove that if $p$ and $q$ are distinct primes such that $pq\mid n^2$ then $pq\mid n$.

Prove that if $p$ and $q$ are distinct primes such that $pq\mid n^2$ then $pq\mid n$. My Attempt: Assume that $pq\nmid n$. If $pq\nmid n$, then $p\nmid n$ or $q\nmid n$. Without loss of generality, ...
0
votes
1answer
28 views

Why do some other people say do for $12$, gro for $144$, and mo for $1,728$ when they use base $12$?

I heard on YouTube that do is some people's word for $12$ in the duodecimal system, but they also say gro for $144$ because it's a gross ($12$ dozens) and mo for $1,728$. I think it's amazing, but ...
0
votes
1answer
34 views

Why do some other people use dek and el rather than letters as the eleventh and twelfth digits in the dozenal or duodecimal system?

I've noticed on a YouTube video titled Base $12$ - Numberphile that some other people who use the duodecimal system use dek and el for the eleventh and twelfth digits. I know for one thing that them ...
0
votes
4answers
50 views

GCD : Why does the GCD of two numbers divides their difference?

I was working my way through some number theoretic proofs and being a newbie am stuck on this proof : Why does the gcd of two numbers , say (a,b) - also divides their difference : a-b My ...
0
votes
2answers
27 views

Prove that if the sum of digits of a number is divisible by 3, so is the number itself.

Here is the proof of the converse: Iff a number $n$ is divisible by $3$, then the sum of its digits is also divisible by $3$. Proof: We know $n \mod 3 = 0$. By the basis representation theorem, $n$ ...
8
votes
1answer
101 views

Division with Gaussian integers

If we are given $A = 7 - 3i, B = 4 + 3i$ and suppose we need to find Gaussian integers $Q, R$ such that $A = QB + R$ with $N(R) < N(B)$ and $N(a + bi) = a^2 + b^2$. OK, so I did the division ...
2
votes
1answer
28 views

Infinite intersection between a arbitrary set of integers and a set of floor powers

Let $E$ be an infinite set of positive integers, proves that there is a $\alpha \in \mathbb{R}$ such that $\{\left \lfloor \alpha^k \right \rfloor ;k \in \mathbb{N} \}\cap E$ is infinite. I have two ...
1
vote
4answers
72 views

Finding 3 variables a,b,c. 31a+30b+28c=365

well, I have this question: Find positive integers $a,b,c$ that solve $$31a+30b+28c=365.$$ Well, it was easy to find them, since i noticed that it actually asks for the months in a year. As, how many ...
1
vote
2answers
49 views

Fermat Numbers Proof [duplicate]

Fermat numbers are shown by: $F_m = 2^{2^m} + 1$. How can I prove that for any $m ≠ n$, I can have $(F_m, F_n) = 1$?
1
vote
3answers
41 views

Set of Numbers with GCD equal to $1$

Can someone give me a set of $4$ positive integers with $3$ of them having a common divisor that is greater than $1$, but the GCD of all four positive integers is $1$.
2
votes
3answers
45 views

Number theory: prove that if $a,b,c$ odd then $2\gcd(a,b,c) = \gcd(a+b,b+c, c+a)$ [closed]

Please help! Am lost with the following: Prove that if $a,b,c$ are odd integers, then $2 \gcd(a,b,c) = \gcd( a+b, b+c, c+a)$ Thanks a lot!!
0
votes
1answer
35 views

Permutations and Combinations Olympiad

Suppose that all positive integers which are relatively prime to 105 are arranged in an increasing sequence - a1 , a2 ,a3 ,.... Evaluate a1000.
0
votes
0answers
55 views

Any conjecture connecting almost $k$-primes and $k$-partitions

Is there any conjecture or similar that suggests that almost $k$-prime can be partitioned into $k$ terms of which $k-1$ are composite and one prime or $k-2$ are composite and 2 prime?
0
votes
0answers
28 views

Evaluating GCD, LCM expression plugging different numbers to get a certain number - where should I stop?

Here's a computer science problem I'm trying to solve: Given an expression tree: type expr = | GCD of expr * expr | LCM of expr * expr | Number of int ...
1
vote
0answers
37 views

Methods for evaluating polynomials quickly

I am wondering what methods exist for effectively evaluating polynomials (manually or in the head) in a quick, efficient fashion. For example, one of my favorite methods is the "nested form of a ...
5
votes
0answers
120 views

Primes as sum of squares.

If $p_{i}$ and $p_{j}$ are two primes of the form $4k+1$ , with $p_{j} > p_{i}$, show that if $p_{j} \neq$ sum of two squares $p_{i}$ is also not equal to sum of two squares. It is well ...
4
votes
3answers
135 views

True or False: $2^{2^{2011}} \text{ divides } 2^{2^{2012} }$

True or false: $$2^{2^{2011}} \text{ divides } 2^{2^{2012} }$$ Give your justifications. I don't know how to start this problem so far. But, I guessed like this, $$2^{\underbrace{2\times ...
0
votes
2answers
34 views

Solve $x^3-ax=by$ If $\gcd(x,y)=1$

Solve the diophantine $x^3-ax=by$ If $\gcd(x,y)=1$. Any hint? My first impression is $\gcd(x,b)>1$ and $x^2=ky+a$ for some integer $m$. I conclude that as long as there exists a square integer ...
0
votes
1answer
44 views

Show that the set $S = \{ax + by : x, y ∈ \mathbb{Z} \} \cap \mathbb{N}$ is not empty

(a) Show that the set $S = \{ax + by : x, y ∈ \mathbb{Z} \} \cap \mathbb{N}$ is not empty. Proof. Notice that if $ a = b = 0$, then $S = \emptyset$, so pick an $a \ne 0$. If $a$ is positive, then ...
3
votes
3answers
286 views

Pythagorean triples

So I am given that $65 = 1^2 + 8^2 = 7^2 + 4^2$ , how can I use this observation to find two Pythagorean triangles with hypotenuse of 65. I know that I need to find integers $a$ and $b$ such that ...
0
votes
3answers
41 views

Help me answer this Number Theory question on GCD (involves exponents) [duplicate]

Basically I need a good hint how to solve the problem.I have solved it partly. $gcd(2^a-1,2^b-1)=2^{gcd(a,b)}-1$. I have reached till: $gcd(2^a-1,2^b-1)=gcd(2^{a-b}-1,2^b-1)$ How to ...