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

learn more… | top users | synonyms

-5
votes
0answers
51 views

Application of chinese remainder theorem [closed]

Solve the systems of linear congruences $ x\equiv 5\pmod 6$ $ x\equiv 4\pmod{11}$ $x\equiv 3\pmod{17} $
-2
votes
0answers
70 views

The Goldbach Conjecture [closed]

Could we consider the Goldbach Function as a proof of the conjecture since for any prime $\psi$ and for any real $\varphi$ ...
0
votes
2answers
35 views
1
vote
1answer
55 views

How find this number of permutation such $|a_{k}-k|\ge\dfrac{n-1}{2}$

let $n$ is give postive integer,Find the number of the $(a_{1},a_{2},\cdots,a_{n})$ be a permutation of $(1,2,3,\cdots,n)$.such $$|a_{k}-k|\ge\dfrac{n-1}{2}$$for any $k=1,2,\cdots,n$ This is ...
0
votes
4answers
37 views

How to calculate the digits of a huge number?

Example, 2^2014 has 607. How many digits in 5^2014? Is there any relation between the two numbers? I found the answer to be 1009 because there exists a pattern in the repeating digits.
0
votes
1answer
37 views

Diophantine equation with condition

The question is to find the general solution in integers $x,y,z$ to $$2x+3y+5z=7$$ where none of $x,y$ or $z$ are divisible by $7$. Without the divisible by $7$ condition I found that the general ...
1
vote
2answers
29 views

Finding digital root of n digit number.

How many steps will be required to find the digital root of a $n$-digit number? E.g., $18$ requires $1$ step but $189$ requires $2$ steps.
0
votes
0answers
25 views

The best generalization of a sequence [closed]

I have an equation, I will build sequences from this equation and I define a generalized equation and look for the best generalization of the sequences ! I will present an example and ask you if it is ...
1
vote
1answer
20 views

General form of Bezout numbers

Bézout's lemma can be generalized to $n$ co-prime integers $a_1, \dots a_n$ : there exists integers $x_1, \dots, x_n$ such that $$a_1 x_1 + \dots + a_n x_n = 1$$ For the case $n = 2$, one can show ...
0
votes
1answer
42 views

Is it possible to prove the existence of an integer with given order while not finding the value itself?

The original question is here: (a)Show that there is an integer a mod 249 whose order is 82. [Hint: If h = ord_m(a), k = ord_n(a) and (m, n) = 1, then ord_mn(a) = [h, k]. ] (b) Show that there is ...
4
votes
1answer
45 views

Proof verification: Let $a$ be an irrational number and $r$ be a nonzero rational number. If $s$ is a rational number then $ar$ + $s$ is irrational

I have to prove the following: Prove: Let $a$ be an irrational number and $r$ be a nonzero rational number. If $s$ is a rational number then $ar$ + $s$ is irrational So, I decided to do a proof ...
1
vote
0answers
16 views

Divisibility via Inclusion-Exclusion

Let $N$ be a large natural number, let $A$ be a subset of naturals, and ask: How many numbers $n\leq N$ are divisible by one or more numbers in $A$. This is a classical application of the ...
0
votes
5answers
49 views

Prove that $p^q+q^p\equiv p+q \mod pq$

I can prove $p^{q-1}+q^{p-1}$ is congruent to 1 mod $pq$ very easily, but with the $p+q$ it doesn't fit a theorem I can find. The only ones I find say if they are congruent to $b$. I get one is ...
1
vote
3answers
92 views

What is the difference between these two propositions? [duplicate]

My text says: Let Evens be the set of even integers greater than 2, and let Primes be the set of primes. Then we can write Goldbach’s Conjecture in logic notation as follows: $ \forall n \in ...
1
vote
1answer
38 views

Confused by a step in a proof that $a^x - b^y = c$ has at most two solutions in positive integers $x,y$

The theorem is Theorem 1.1 from Michael A. Bennett in his "On Some Exponential Equations of S.S. Pillai". Here is the statement of the theorem: Theorem 1.1. If $a,b,c$ are nonzero integers with $a,b ...
4
votes
1answer
73 views

How can I prove that $\frac{\sigma(n)}{n} = \sum_{(d|n)} \frac{1}{d}$ for every $n \in \mathbb{Z^{+}}$?

I want to show that $\displaystyle \frac{\sigma(n)}{n} = \sum_{(d|n)} \frac{1}{d}$ for every $n \in \mathbb{Z^{+}}$. This is essentially a basic number theory question. I am able to get to the ...
1
vote
2answers
46 views

Is there a method to solve the diophantine equation of the form $x^2 - ay +1 =0$, where $a \in \mathbb{N}$?

As the title says, is there a standard method to obtain a set of solutions for the Diophantine equation? Thank you.
0
votes
1answer
23 views

Figuring out a range with given values

firstly my math is terrible :( I need to figure out a formulae for an app I am making I need to figure out the spacing between objects Firstly I will have minimum pages of 3 to a max 20 If I have ...
0
votes
1answer
34 views

Evaluate smartly a function on a multiplication grid

I am asking myself the following question: Suppose one has a grid $G \in \mathbb{N}^{n\times n}$ where $g_{ij} = i\cdot j$, $i,j \leq n$. I would like to evaluate a function $f: G \to \mathbb{N}$. ...
2
votes
0answers
22 views

Where can I find proof - There're infinitely many primes $p$ such that $p(mod\ N)\not\in H$ - Name?

Origin - http://math.uga.edu/~pete/4400FULL.pdf - on p120, Theorem 122 Fix a positive integer $N>2$, and let $H$ be a proper subgroup of $U(N)=(Z/NZ)^{\times}$. There are infinitely many ...
1
vote
0answers
30 views

If $d(n)$ is the sum of digits of n, find $d(d(d(n)))$ of $n=4444^{4444}$ [duplicate]

If $d(n)$ is the sum of digits of n, find $d(d(d(n)))$ of $n=4444^{4444}$. My attempt: $4444^{4444}<10000^{4444}$ Now, $\max d(10000^{4444})<9\times 17776$ Again, $\max d(159984)\le ...
1
vote
3answers
39 views

Question on solution for 2013 USAJMO #1

The problem and solution can be viewed here My question is on the part where they state If $a^5b\equiv 6\pmod 9$, then note that $3|b$. This is because if $3|a$ then $a^5b\equiv 0\pmod 9$. I ...
0
votes
0answers
61 views

Is my proof good enough?

Prove: The product of any three consecutive natural numbers is divisible by 6. 6|n (n+1) (n+2). If n is an odd number (n=(2 t+1), t is any natural number), then (n+1)= ((2 t+1)+1) an even number. So ...
0
votes
5answers
58 views

Finding $7$ inverse modulo $11$

I'm trying to find the inverse of $7$ modulo $11$. From what I understand, the steps are: \begin{align} &11 = 1(7) + 3 \\ &7 = 2(3) + 1 \\ \end{align} From here, you work backwards ...
0
votes
1answer
13 views

prove that $(k,mn)=(k,m)(k,n)$ $\forall k\in \mathbb Z$ and $(m,n)=1$:

prove that $(k,mn)=(k,m)(k,n)$ $\forall k\in \mathbb Z$ and $(m,n)=1$: My attempt: let $b=(k,m)$, $c=(k,n)$ and $a=(k,mn)$then there exist $x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}\in \mathbb Z$ so that ...
0
votes
2answers
15 views

prove that $\forall k\in \mathbb Z$ if $(m,n)=1$(coprimes) then $(k,m,n)=1$

Prove that $\forall k\in \mathbb Z$ if $(m,n)=1$(coprimes) then $(k,m,n)=1$ I did this by contradiction: let $d=(k,m,n)$ so that $d\neq 1$; by definition of greatest common divisor $d|k, d|m, d|n$ ...
0
votes
3answers
48 views

Solving the congruence $7x \equiv 41 \mod{13}$

I have to solve the following linear congruence: $$7x \equiv 41 \mod{13}$$ The question where I got this from comes in two parts. The first is that it asks to find the set of the inverses of $7 ...
0
votes
1answer
29 views

About an equality involving prime numbers

Let two primes : $p_1$ and $p_2$. I have $\alpha$ and $\beta$ two rationals and $b$ an integer with $$4b=-(\alpha+1)(p_1-p_2)=-(\beta+1)(p_1+p_2)$$ Thus $$(\alpha-\beta)p_1=(\alpha+\beta+2)p_2$$ Is ...
0
votes
1answer
44 views

Remainder of $1946^{1972} : 26$

Is this correct? $1946^1 = 22 \mod{26}$ $1946^2 = 22^2 = 484 = 16\mod{26}$ $1946^3 = 22^2 * 22 = 16 * 22 = 14 \mod{26}$ $1946^4 = 22^2 * 22^2 = 16^2 = 22 \mod{26}$ And therefore for any integer ...
-1
votes
5answers
102 views

Is this a true theorem? [closed]

I'm trying to prove the existence of the following theorem: If $n,p \in \mathbb{N}$, then $(p+1)^n = 1 \mod p$ Is this theorem true? I think it is, but I don't know how to prove it! Thanks!
0
votes
2answers
46 views

Proving divisibility tests using congruence relations [closed]

For a positive integer $N$ which has the decimal representation $$N=\sum_{k=0}^n a_k\cdot10^k $$ Prove that $$11\mid N \Longleftrightarrow 11\mid \sum_{k=0}^n(-1)^k a_k $$ using congruence ...
2
votes
3answers
42 views

Logical structure of elementary number theoretic proof

I'm trying to understand the detailed logic structure of a proof by use of the bezout identity.The number theoretic part i easily understand, the problem i'm having is with the logic. One example ...
2
votes
2answers
75 views

application of Fermat's little theorem

show that $a^{13} \equiv a\mod 35$ using Fermat's little theorem. Use Fermat's little theorem with primes 5 and 7. $a^7 \equiv a (mod 7$) and $a^5 \equiv a (mod 5$)
2
votes
4answers
66 views

Contest problem involving primes and factorization

Prove that for any nonnegative integer $n$, the number $$5^{5^{n+1}}+ 5^{5^{n}}+1$$ is not prime. I want only some hints and the method to follow, but I don't need the full solution. Thanks.
-1
votes
0answers
206 views

Is this proof of Fermat correct? [closed]

Beside the proof of Catalan detailed in my other post, I wonder if Fermat equation, like Catalan's one, can not be solved like this ? Let Fermat equation : $$Y^n=X^n+Z^n$$ I pose ...
0
votes
1answer
39 views

Euclid's first theorem/ Euclid's lemma

How to prove that if $c$ divides $ab$ and $\operatorname{gcd}(a,c)=1$, then show that $c$ divides $b$. that means if $c|ab$ and $(a,c)=1 \implies c|b$.
0
votes
1answer
43 views

An additive property of integers

Let $a_0, p$ be any positive integers,defining: $$a_{n+1} = \begin{cases}\frac{a_n}{p} &, a_n \text{ divisible by p}\\ a_n + k_n/l_n/o_n.. &, a_n \text{ odd}. \end{cases}$$ Now choose the ...
0
votes
0answers
55 views

What's a name for this elementary number theory lemma? Where can I find it online?

I was going to ask another question about this - Origin - Elementary Number Theory, Jones, p23, Lemma 2.4 - but then I chanced on If a product of relatively prime integers is an $n$th power, then each ...
0
votes
1answer
25 views

Proof - Fundamental Theorem of Arithmetic using Euclid's Lemma

Let $n \in Z > 1$. Then the expression for $n$ as the product of $\ge 1$ primes is unique, up to the order in which they appear. From Proofwiki. Suppose $n$ has two prime factorizations: ...
0
votes
1answer
16 views

Need help in understanding $ord_p{a}$ as used in Theorem 1.1 from “On Some Exponential Equations Of S. S. Pillai”

I have a question about very early argument in the proof of Thereom 1.1. Theorem 1.1 of On Some Exponential Equations of S.S. Pillai states that if $a,b,c$ are nonzero integers with $a,b \ge 2$, then ...
1
vote
0answers
57 views

Proof Synopsis of Fermat's Last Theorem

I'm taking a introduction to higher math course now (mostly number theory) and our professor wants us to include two sentence proof synopses with our longer proofs. This got me thinking, What is a ...
1
vote
1answer
23 views

Linear diophantine equation word problem

I have the following word problem: A small clothing manufacturer produces two styles of sweaters: cardigan and pullover. She sells cardigans for $\$31$ each and pullovers for $\$28$ each. If her ...
1
vote
2answers
39 views

Given a finite abelian group $G$ with $g \in G$, then for any divisor $d$ of $|g|$ there is an element of $G$ with order $d$.

From an homework question that comes as an introduction to abelian groups. Regarding my efforts to solve the question, I have been trying to utilize the fundamental theorem of finite abelian groups, ...
2
votes
2answers
92 views

Prime numbers like 113

The number 113 is prime. The sum, product and all permutations of it's digits are prime. Are there any other such prime numbers?
0
votes
0answers
19 views

Find the general solution to diophantine equation $-221x + 187y - 493 = 0$

I have to find the general solution to $$-221x + 187y - 493 = 0$$ The main issue, I'm figuring out if I have found the general solution or not. Below, are my steps: The $\gcd{(-221,187)} = 17$ and ...
0
votes
3answers
45 views

If $a,b < p$, then $p \nmid ab$?

I'm trying to prove that if there two positive integers $a$ and $b$ such that they are less than a prime number $p$, then the product $ab$ will not be divisible by $p$. I know there must be multiple ...
0
votes
1answer
17 views

Find integers $k$ and $l$ such that $\gcd(-5775,-651)$ can be expressed in the form $ka + bl$

As the title suggests, I have to find the following: $k$ and $l$ such that $\gcd(-5775,-651)$ can be expressed in the form $ka + bl$ Now, the main issue, I have is figuring out how the negatives ...
0
votes
6answers
70 views

Find all solutions to $a^{2003} \equiv 1 \mod{17}$

Through messing around with numbers, I found that $a \equiv 1\mod{17}$. How would you obtain this answer? Thanks!
0
votes
2answers
27 views

Find all solutions to $x^3-x^2+2x-2=0 \pmod {11}$

I get that $11$ is a small number and that I could maybe do this by inspection, but I was wondering if there was a more intelligent approach?
0
votes
1answer
34 views

Find the last two digits of the number 9^9^9

Find the last two digits of the number 9^9^9 . [Hint: 9^9 ≡ 9 (mod 10) ; hence, 9^9^9 = 9^9+10k ;now use the fact that 9^9 ≡ 89 (mod 100)]