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

learn more… | top users | synonyms

6
votes
3answers
539 views

$\tbinom{2p}{p}-2$ is divisible by $p^3$

The problem is as follows: Let $p>3$ be a prime. Show that $\tbinom{2p}{p}-2$ is divisible by $p^3$. The only thing I can think of is that $(2p)!-2(p!)^2$ is divisible by $p^2$ which doesn't help ...
3
votes
6answers
435 views

Prove if $x^{2}-5xy-3$ is even, then $x+y$ is odd, where $x,y \in\mathbb{Z}$

I know for you this is easy but for me is not. I give my best shot but it's no use so I need someone to teach about all this stuff. As I try to solve this one, I come up with this answer: Suppose ...
5
votes
3answers
99 views

Why does $\{1\cdot a\! \! \pmod p, 2\cdot a\! \! \pmod p,\ldots, (p-1)\cdot a\! \! \pmod p\}$ $= \{1, 2,\ldots, p-1\}$ when $a$ and $p$ are coprime?

Why is it that $\{1\cdot a \pmod p, 2\cdot a \pmod p,\ldots, (p-1)\cdot a \pmod p\} = \{1, 2,\ldots, p-1\}$ (albeit in a different order) when a and p are coprimes? I can't figure this out and I've ...
10
votes
3answers
332 views

Finding the sum of the digits of $3^{1000}$ [closed]

Can we work out the sum of the digits of the number $3^{1000}$ without any program? I just means the way of pure mathematics. I'm interested in learning more way to solve this problem.Let's solve it ...
3
votes
1answer
76 views

factors of an equation

I want to write a code which boils down to equation $(x y) = (x + y) N$. My task is to find all the possible integer (natural number) solutions for $x$ and $y$. For example, say $N=6$. As $x$ and ...
3
votes
4answers
263 views

Prove that there exists a natural number n for which $11\mid (2^{n} - 1)$

I'm thinking putting it into modulo form: there exists a natural number $n$ for which $$2^{n}\equiv 1 \pmod {11}$$ but I don't know what to do next and I'm still confused how to figure out ...
4
votes
6answers
1k views

Prove that , any primitive root $r$ of $p^n$ is also a primitive root of $p$

For an odd prime $p$, prove that any primitive root $r$ of $p^n$ is also a primitive root of $p$ So I have assumed $r$ have order $k$ modulo $p$ , So $k|p-1$.Then if I am able to show that ...
8
votes
2answers
189 views

How to find all naturals $n$ such that $\sqrt{1 {\underbrace{4\cdots4}_{n\text{ times}}}}$ is an integer?

How to find all naturals $n$ such that $\sqrt{1\smash{\underbrace{4\cdots4}_{n\text{ times}}}}$ is an integer?
0
votes
3answers
422 views

Which is the biggest integer that divides all integers that are the product of three consecutive odd numbers?

I read this problem from a high-school-math-problems-calendar, and I'm solving them in my spare time just for the fun of it (what in math is not about the fun? =) ), but this little one it's been hard ...
1
vote
4answers
112 views

Divisibility proof involving substitution

I’m having trouble with the proving the following: If $a \mid b-2c$ and and $a \mid 2b+3c$ then $a \mid b$ and $a \mid c$. Heres my partial solution: By definition of divisibility, $b-2c=ak$ ...
1
vote
2answers
127 views

integer sequences

Is anybody aware if there exists good computer software which tries to find, in a brute force manner, patterns in given finite sequences of numbers. For example , if you would give the Fibonacci ...
1
vote
3answers
269 views

How to prove $p$ divides $a^{p - 2} + a^{p - 3} b + a^{p - 4} b^2 + \cdots + b^{p - 2}$ when $p$ is prime, $a, b \in \mathbb{Z}$ and $a,b \lt p$?

If $p$ is a prime number and $a, b \in \mathbb{Z}$ such that $a,b \lt p$, then how could we prove that $p$ divides $\left(a^{p - 2} + a^{p - 3} b + a^{p - 4} b^2 + \cdots + b^{p - 2}\right)$?
0
votes
1answer
178 views

Application of Pell's equation

Need to find $n,r$ (if any) for $121^r-2n^2=1$ where $n,r$ are natural numbers. Observed that $n$ is odd then $n=2m+1$ (say). But on replacement of $n$ by $2m+1$, increases the complexity of the ...
0
votes
3answers
585 views

Roots of a polynomial mod $n$

Let $n=n_1n_2\ldots n_k$ where $n_i$ are pairwise relatively prime. Prove for any polynomial $f$ the number of roots of the equation $f(x)\equiv 0\pmod n$ is equal to the product of the number of ...
3
votes
3answers
755 views

Show that the product of the $\phi(p-1)$ primitive roots of $p$ is congruent modulo $p$ to $(-1)^{\phi(p-1)}$

If $p$ is a prime, show that the product of the $\phi(p-1)$ primitive roots of $p$ is congruent modulo $p$ to $(-1)^{\phi(p-1)}$. I know that if $a^k$ is a primitive root of $p$ if ...
3
votes
2answers
62 views

Solve $k_1 a = k_2 b + c$

Find all $k_1, k_2$ that satisfy $k_1 a = k_2 b + c$ where everything are integers. It feels like there should be some easy way to describe this in terms of congruence and gcd.
4
votes
3answers
136 views

$(a+b+c)^p-(a^p+b^p+c^p)$ is always divisible by…?

$(a + b + c)^p - (a^p + b^p + c^p)$ is always divisible by (a) $p - 1\quad$ (b) $a + b + c\quad$ ( c ) $p\quad$ ( d ) $p^2 - 1$ $p$ is prime I am able to solve this by substituting values ...
1
vote
1answer
176 views

Irrational distances, rational area triangles

Given any positive integer $n\ge3$ how to show that there are $n$ distinct points in the plane such that 1- the distance between any two points is irrational number and 2- each set of three points ...
2
votes
2answers
84 views

Condition(s) that satisfy this equality

I am having difficulty understanding how my book came up with this answer. Define $a \star b =ab+2b$, and suppose $x \star y = y \star x$. Then which of the following must be true? A. ...
2
votes
3answers
265 views

When is $(6a + b)(a + 6b)$ a power of two?

Find all positive integers $a$ and $b$ for which the product $(6a + b)(a + 6b)$ is a power of $2$. I havnt been able to get this one yet, found it online, not homework! any help is appreciated ...
5
votes
3answers
236 views

Further reading on the $p$-adic metric and related theory.

In his book Introduction to Topology, Bert Mendelson asks to prove that $$(\Bbb Z,d_p)$$ is a metric space, where $p$ is a fixed prime and $$d_p(m,n)=\begin{cases} 0 \;,\text{ if }m=n \cr ...
3
votes
1answer
260 views

$\alpha x^2+\beta y^2=\gamma$ solvable over $\mathbb Q$ iff $ax^2+by^2=z^2$ solvable over $\mathbb Z$ with coprime $x,y,z$?

I want to understand an algorithm from [1] to solve $$\alpha x^2+\beta y^2=\gamma \text{ over } \mathbb{Q}$$ with $\alpha, \beta, \gamma\in\mathbb{Q}$. As far is I understood the process the ...
0
votes
0answers
65 views

Calculating A from this equation

I am having trouble with the following question If A and B are positive integers and $A^2 + B^2 = 36$ Then what is $A$? The choices are 6, 7, 8, 9, or 10. How does one show that answer ...
3
votes
2answers
1k views

Prove three things related to the GCD

I have to demonstrate this three formulae: $\gcd(ac,bc)=c\gcd(a,b), \forall a,b,c \in \mathbb{N}$ $a\mid c \land b\mid c \land \gcd(a,b)=1 \implies ab\mid c$ $\gcd(a,b,c)=xa+yb+zc, \forall ...
1
vote
2answers
210 views

Recursive digit-sum

Let the recursive digit-sum(R.D.) be defined as: continue taking the sum of digits until it becomes <10. For example, the digit-sum of 5987 = 29, the digit-sum of 29 =11 So, R.D. of 5987 is 2. ...
1
vote
1answer
272 views

Algorithm for generating an ordered list of pair products

For problem 4 in the euler project part of the assignment is to generate a list of products of 3-digit numbers. The easy way is to just do a cartesian product (I think it's called), and after that ...
-4
votes
2answers
106 views

Find third value

I have a very simple problem but I feel like I am brain-dead. I cant figure it out how to calculate this in Java: 1321 = 0 1771 = 640 1500 = ? Thanks. Edit: ...
1
vote
3answers
88 views

if $ax \equiv 1 \pmod{y}$ and $by \equiv 1 \pmod{x}$, then gcd$(x,y)=1$

I don't think someone has posted this question yet. One looks similar, but I wasn't sure. Sorry in advance if it is. I think I am making things up toward the end. I wanted to make a squeeze ...
2
votes
2answers
57 views

if $ax+by = d$, then $a'x+b'y=d$ where $x>0$ and $0 \leq b' \leq x$

I've been trying this for a little while now, if $ax+by = d, \ $ then $a'x+b'y=d$ where $x>0\ $ and $0 \leq b' \leq x\ $ and $a,b,a',b',x,y, \in \mathbb{Z}$ My first thought is: $$ ...
6
votes
4answers
655 views

Fractional Binomial Coefficients

I recently examined the binomial coefficient $\binom{\frac{1}{2}}{k}$ and found that the denominator was always a power of two. The same is true of $\binom{\frac{1}{3}}{k}$, where the denominator is ...
0
votes
2answers
58 views

Security of a particular cryptosystem

I recently came across this problem, and while I'm fairly certain the solution is not too 'conceptually-challenging', I've been stumped at finding the right trick/manipulation to make any solution ...
7
votes
5answers
355 views

Can $a^2+b^2+2ac$ be a perfect square if $c\neq \pm b$?

Can $a^2+b^2+2ac$ be a perfect square if $c\neq \pm b$? $a,b,c \in \mathbb{Z}$. I have tried some manipulations but still came up with nothing. Please help. Actual context of the question is: ...
5
votes
2answers
126 views

finding all integer $n$ such that $ n\mid2^{n!}-1$

how to find all integer $n$ such that $ n\mid2^{n!}-1$ I find: Of course $2 \nmid n$. We prove that, if $2 \nmid n$ then $n \mid 2^{n!}-1$. $2 \nmid n \iff n = 2k+1 , k \ge 0$, we'll prove: ...
4
votes
3answers
930 views

A problem dealing with even perfect numbers.

Question: Show that all even perfect numbers end in 6 or 8. This is what I have. All even perfect numbers are of the form $n=2^{p-1}(2^p -1)$ where $p$ is prime and so is $(2^p -1)$. What I did was ...
3
votes
1answer
143 views

$a+d=2^k,b+c=2^m$,proving $a=1$

$a<b<c<d$ are odd natural numbers. $ad=bc$ $a+d=2^{k},b+c=2^{m}$ how to prove that $a=1$ I heard that we can prove it by "Four Number Theorem" ,is that right? And is there a different way ...
4
votes
1answer
137 views

If $p$ is a prime and $x,y \in \mathbb{Z}$, then $(x+y)^p \equiv x^p+y^p \pmod{p}$

I want to prove that if $p$ is a prime and $x,y \in \mathbb{Z}$, then $$(x+y)^p \equiv x^p+y^p \pmod{p}$$ So far I know that $$(x+y)^p = \sum_{k=0}^{p} \dbinom{p}k x^{p-k} y^k$$ A part of the above ...
2
votes
2answers
281 views

Given $r$ and $s$ litre jugs, $m$ litres of water can be measured for any positive integer $m$

The problem is: Show that it is possible to measure any integral number of litres using only a $3$ litre and a $7$ litre jug. And then the book says it's true that given $r$ and $s$ litre jugs, ...
0
votes
4answers
181 views

$nx - my = 0$, find smallest positive integer values of $nx$ and $my$ where this is true

My first question on math stackexchange. I have two numbers, $n$ and $m$. Their values will vary but I always know what they are and they're always positive integers (and multiples of 2, but that ...
1
vote
0answers
113 views

How to find the last two digits of $9^{9^{9^9}}$? [duplicate]

Possible Duplicate: The last two digits of $9^{9^9}$ How to find the last two digits of $9^{9^{9^9}}$ (a power tower of 4 $9$'s) ? Is there any special approach to these kind of problems?
34
votes
1answer
1k views

Decomposing polynomials with integer coefficients

Can every quadratic with integer coefficients be written as a sum of two polynomials with integer roots? (Any constant $k \in \mathbb{Z}$, including $0$, is also allowed as a term for simplicity's ...
1
vote
0answers
45 views

A question regarding the method followed in Cohen & Selfridge's paper on covering systems.

Note: I have posted this question on MO before. No one replied, so I am reposting it here. I am reading this paper by Cohen and Selfridge that deals with covering systems. Its link is ...
2
votes
2answers
127 views

showing a quadratic residue

Let $p\equiv3\pmod4$ be prime and $p \nmid x$. How can you show that a quadratic residue modulo $p$ is given by $x$ or $-x$ ? Thanks!
3
votes
1answer
594 views

Change of order of summation.

I feel like an idiot for asking this, so bear my stupidity. I have the sum $\sum_{n\leq N} \sum_{p | n ; \ p \ prime} 1$, and I want to change the order of summation of these two sums I think it ...
1
vote
1answer
97 views

for $n=x^2+3y^2$ , $n=\prod p^{a(p)}$ , $a(p)$ is even for all $p \equiv 2 \pmod 3$ where $p$ is prime

I'd really like your help with the following Number Theory question: I need to show that if I can write an integer $n=x^2+3y^2$ so in the factorization of $n$ to primes, every $p \equiv 2\pmod 3$ ...
3
votes
2answers
340 views

Squares of the form $x^2+y^2+xy$

How can I find all $(a,b,c) \in \mathbb{Z}^3$ such that $a^2+b^2+ab$, $a^2+c^2+ac$ and $b^2+c^2+bc$ are squares ? Thanks !
1
vote
1answer
71 views

Does $k$-th power of $p$ divide ${}_n\!C_r$ if the previous divides $n$?

Does $p^k$ divide ${}_n\!C_r$ for all integer r if $p^k|n$ where $0\leq r \leq n$ and $p$ is prime?
3
votes
4answers
172 views

solving the congruence: $5^n\equiv3^n+2 \pmod{11}.$

I'd really like your help with solving the following congruence: $$5^n\equiv3^n+2 \pmod{11}.$$ I don't know with what to start. Any help? Thanks
6
votes
4answers
1k views

Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them

Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them. Let $a$ be the primitive root then I know other primitive roots will be among $\{a,a^2,a^3 \cdots\cdots a^{\phi(n)} ...
2
votes
2answers
1k views

Prove/Show that a number is square if and only if its prime decomposition contains only even exponents.

Prove/Show that a number is square if and only if its prime decomposition contains only even exponents. How would you write a formal proof for this.
9
votes
11answers
3k views

If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$

This seems clear, but I don't know how to prove this.. I was trying to show this by induction such that if $a^{n+1}$ = $rs$ and $b^{n+1}$ = $rt$, then $s,t$ are divisible by $a,b$ respectively, but i ...