Elementary number theory, prime numbers

up vote
3
down vote

favorite

Let $p$ and $q$ be two different prime numbers, and $a$ a positive integer. Show that $A$ = $a^pq$ - $a^p$ - $a^q$ + $a$ can be divided by $pq$

I started by rewriting $A$ as : (($a^p)^q$ - $a^p$) - ($a^q$ - $a$) but I'm not sure how to go from here

edited 1 hour ago

asked 1 hour ago

Alli Henne

356

There is a contradiction in your formulas; the first one has $-a^q-a^q$, the second has $-a^p-a^q$. Do you know little Fermat?
â€“Â Dietrich Burde
1 hour ago

1

Use Euler's theorem.
â€“Â Jakobian
1 hour ago

add a commentÂ |Â

up vote
3
down vote

favorite

Let $p$ and $q$ be two different prime numbers, and $a$ a positive integer. Show that $A$ = $a^pq$ - $a^p$ - $a^q$ + $a$ can be divided by $pq$

I started by rewriting $A$ as : (($a^p)^q$ - $a^p$) - ($a^q$ - $a$) but I'm not sure how to go from here

edited 1 hour ago

asked 1 hour ago

Alli Henne

356

There is a contradiction in your formulas; the first one has $-a^q-a^q$, the second has $-a^p-a^q$. Do you know little Fermat?
â€“Â Dietrich Burde
1 hour ago

1

Use Euler's theorem.
â€“Â Jakobian
1 hour ago

add a commentÂ |Â

up vote
3
down vote

favorite

Let $p$ and $q$ be two different prime numbers, and $a$ a positive integer. Show that $A$ = $a^pq$ - $a^p$ - $a^q$ + $a$ can be divided by $pq$

I started by rewriting $A$ as : (($a^p)^q$ - $a^p$) - ($a^q$ - $a$) but I'm not sure how to go from here

edited 1 hour ago

asked 1 hour ago

Alli Henne

356

Let $p$ and $q$ be two different prime numbers, and $a$ a positive integer. Show that $A$ = $a^pq$ - $a^p$ - $a^q$ + $a$ can be divided by $pq$

I started by rewriting $A$ as : (($a^p)^q$ - $a^p$) - ($a^q$ - $a$) but I'm not sure how to go from here

elementary-number-theory prime-numbers arithmetic

edited 1 hour ago

asked 1 hour ago

Alli Henne

356

edited 1 hour ago

asked 1 hour ago

Alli Henne

356

edited 1 hour ago

asked 1 hour ago

Alli Henne

356

asked 1 hour ago

Alli Henne

356

asked 1 hour ago

Alli Henne

356

There is a contradiction in your formulas; the first one has $-a^q-a^q$, the second has $-a^p-a^q$. Do you know little Fermat?
â€“Â Dietrich Burde
1 hour ago

1

Use Euler's theorem.
â€“Â Jakobian
1 hour ago

add a commentÂ |Â

There is a contradiction in your formulas; the first one has $-a^q-a^q$, the second has $-a^p-a^q$. Do you know little Fermat?
â€“Â Dietrich Burde
1 hour ago

1

Use Euler's theorem.
â€“Â Jakobian
1 hour ago

There is a contradiction in your formulas; the first one has $-a^q-a^q$, the second has $-a^p-a^q$. Do you know little Fermat?
â€“Â Dietrich Burde
1 hour ago

Use Euler's theorem.
â€“Â Jakobian
1 hour ago

add a commentÂ |Â

3 Answers
3

active

oldest

votes

up vote
4
down vote

accepted

It suffices to show that both $p$ and $q$ divide$$a^pq-a^p-a^q+a $$

Note that $$a^p equiv a mod (p)$$ therefore $$a^pq equiv a^q mod (p)$$Thus $$a^pq-a^p-a^q-a equiv a^q-a^p-a^q+a equiv 0 mod (p)$$

Similarly we can show that $$a^pq-a^p-a^q-a equiv 0 mod (q)$$

answered 1 hour ago

Mohammad Riazi-Kermani

37k41956

add a commentÂ |Â

up vote
2
down vote

Use little Fermat, if $p$ is a prime number and $a$ a intenger then
$p|(a^p - a)$

So, $p|((a^q)^p - a^q$), and $p|(a^p - a)$

Then $p$ divides the difference, $p|((a^q)^p - a^q - a^p + a)$

Doing the same for $q$, we have $q|((a^p)^q - a^p - a^q + a)$

Then as $(p,q) = 1$, we have $pq|(a^pq - a^p - a^q + a)$

Well, $(p,q) = 1$, then there exists $s,t in mathbbZ$ such that $1 = ps + qt$

So if $p|c$ and $q|c$, then $ c = pk = qr$, with $k,r in mathbbZ$ then $c = c.1 = c(ps + qt) = cps + cqt = qrps + pkqt) = qp (rs + kt)$

Then $pq|c$

edited 45 mins ago

answered 1 hour ago

ZAF

212

New contributor

add a commentÂ |Â

up vote
1
down vote

I suppose you mean $pq$ divides $, a^pq-a^p-a^q+a$, i.e.
$$ a^pq-a^p-a^q+aequiv 0pmodpq.$$

Hint:

By the Chinese remainder theorem, it amounts to proving it is congruent to $0$ $bmod p$ and $bmod q$.

As $p$ and $q$ are prime, remember Little Fermat can be formulated as
$$forall a,: a^pequiv apmod p$$
and similarly for $q$.

answered 1 hour ago

Bernard

114k637106

add a commentÂ |Â

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\$","\$"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2976402%2felementary-number-theory-prime-numbers%23new-answer', 'question_page');

);

Post as a guest

Name

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

up vote
4
down vote

accepted

It suffices to show that both $p$ and $q$ divide$$a^pq-a^p-a^q+a $$

Note that $$a^p equiv a mod (p)$$ therefore $$a^pq equiv a^q mod (p)$$Thus $$a^pq-a^p-a^q-a equiv a^q-a^p-a^q+a equiv 0 mod (p)$$

Similarly we can show that $$a^pq-a^p-a^q-a equiv 0 mod (q)$$

answered 1 hour ago

Mohammad Riazi-Kermani

37k41956

add a commentÂ |Â

up vote
4
down vote

accepted

It suffices to show that both $p$ and $q$ divide$$a^pq-a^p-a^q+a $$

Note that $$a^p equiv a mod (p)$$ therefore $$a^pq equiv a^q mod (p)$$Thus $$a^pq-a^p-a^q-a equiv a^q-a^p-a^q+a equiv 0 mod (p)$$

Similarly we can show that $$a^pq-a^p-a^q-a equiv 0 mod (q)$$

answered 1 hour ago

Mohammad Riazi-Kermani

37k41956

add a commentÂ |Â

up vote
4
down vote

accepted

It suffices to show that both $p$ and $q$ divide$$a^pq-a^p-a^q+a $$

Note that $$a^p equiv a mod (p)$$ therefore $$a^pq equiv a^q mod (p)$$Thus $$a^pq-a^p-a^q-a equiv a^q-a^p-a^q+a equiv 0 mod (p)$$

Similarly we can show that $$a^pq-a^p-a^q-a equiv 0 mod (q)$$

answered 1 hour ago

Mohammad Riazi-Kermani

37k41956

It suffices to show that both $p$ and $q$ divide$$a^pq-a^p-a^q+a $$

Note that $$a^p equiv a mod (p)$$ therefore $$a^pq equiv a^q mod (p)$$Thus $$a^pq-a^p-a^q-a equiv a^q-a^p-a^q+a equiv 0 mod (p)$$

Similarly we can show that $$a^pq-a^p-a^q-a equiv 0 mod (q)$$

answered 1 hour ago

Mohammad Riazi-Kermani

37k41956

answered 1 hour ago

Mohammad Riazi-Kermani

37k41956

answered 1 hour ago

Mohammad Riazi-Kermani

37k41956

answered 1 hour ago

Mohammad Riazi-Kermani

37k41956

add a commentÂ |Â

up vote
2
down vote

Use little Fermat, if $p$ is a prime number and $a$ a intenger then
$p|(a^p - a)$

So, $p|((a^q)^p - a^q$), and $p|(a^p - a)$

Then $p$ divides the difference, $p|((a^q)^p - a^q - a^p + a)$

Doing the same for $q$, we have $q|((a^p)^q - a^p - a^q + a)$

Then as $(p,q) = 1$, we have $pq|(a^pq - a^p - a^q + a)$

Well, $(p,q) = 1$, then there exists $s,t in mathbbZ$ such that $1 = ps + qt$

So if $p|c$ and $q|c$, then $ c = pk = qr$, with $k,r in mathbbZ$ then $c = c.1 = c(ps + qt) = cps + cqt = qrps + pkqt) = qp (rs + kt)$

Then $pq|c$

edited 45 mins ago

answered 1 hour ago

ZAF

212

New contributor

add a commentÂ |Â

up vote
2
down vote

Use little Fermat, if $p$ is a prime number and $a$ a intenger then
$p|(a^p - a)$

So, $p|((a^q)^p - a^q$), and $p|(a^p - a)$

Then $p$ divides the difference, $p|((a^q)^p - a^q - a^p + a)$

Doing the same for $q$, we have $q|((a^p)^q - a^p - a^q + a)$

Then as $(p,q) = 1$, we have $pq|(a^pq - a^p - a^q + a)$

Well, $(p,q) = 1$, then there exists $s,t in mathbbZ$ such that $1 = ps + qt$

So if $p|c$ and $q|c$, then $ c = pk = qr$, with $k,r in mathbbZ$ then $c = c.1 = c(ps + qt) = cps + cqt = qrps + pkqt) = qp (rs + kt)$

Then $pq|c$

edited 45 mins ago

answered 1 hour ago

ZAF

212

New contributor

add a commentÂ |Â

up vote
2
down vote

Use little Fermat, if $p$ is a prime number and $a$ a intenger then
$p|(a^p - a)$

So, $p|((a^q)^p - a^q$), and $p|(a^p - a)$

Then $p$ divides the difference, $p|((a^q)^p - a^q - a^p + a)$

Doing the same for $q$, we have $q|((a^p)^q - a^p - a^q + a)$

Then as $(p,q) = 1$, we have $pq|(a^pq - a^p - a^q + a)$

Well, $(p,q) = 1$, then there exists $s,t in mathbbZ$ such that $1 = ps + qt$

So if $p|c$ and $q|c$, then $ c = pk = qr$, with $k,r in mathbbZ$ then $c = c.1 = c(ps + qt) = cps + cqt = qrps + pkqt) = qp (rs + kt)$

Then $pq|c$

edited 45 mins ago

answered 1 hour ago

ZAF

212

New contributor

Use little Fermat, if $p$ is a prime number and $a$ a intenger then
$p|(a^p - a)$

So, $p|((a^q)^p - a^q$), and $p|(a^p - a)$

Then $p$ divides the difference, $p|((a^q)^p - a^q - a^p + a)$

Doing the same for $q$, we have $q|((a^p)^q - a^p - a^q + a)$

Then as $(p,q) = 1$, we have $pq|(a^pq - a^p - a^q + a)$

Well, $(p,q) = 1$, then there exists $s,t in mathbbZ$ such that $1 = ps + qt$

So if $p|c$ and $q|c$, then $ c = pk = qr$, with $k,r in mathbbZ$ then $c = c.1 = c(ps + qt) = cps + cqt = qrps + pkqt) = qp (rs + kt)$

Then $pq|c$

edited 45 mins ago

answered 1 hour ago

ZAF

212

New contributor

edited 45 mins ago

answered 1 hour ago

ZAF

212

New contributor

answered 1 hour ago

ZAF

212

answered 1 hour ago

ZAF

212

New contributor

ZAF is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

add a commentÂ |Â

up vote
1
down vote

I suppose you mean $pq$ divides $, a^pq-a^p-a^q+a$, i.e.
$$ a^pq-a^p-a^q+aequiv 0pmodpq.$$

Hint:

By the Chinese remainder theorem, it amounts to proving it is congruent to $0$ $bmod p$ and $bmod q$.

As $p$ and $q$ are prime, remember Little Fermat can be formulated as
$$forall a,: a^pequiv apmod p$$
and similarly for $q$.

answered 1 hour ago

Bernard

114k637106

add a commentÂ |Â

up vote
1
down vote

I suppose you mean $pq$ divides $, a^pq-a^p-a^q+a$, i.e.
$$ a^pq-a^p-a^q+aequiv 0pmodpq.$$

Hint:

By the Chinese remainder theorem, it amounts to proving it is congruent to $0$ $bmod p$ and $bmod q$.

As $p$ and $q$ are prime, remember Little Fermat can be formulated as
$$forall a,: a^pequiv apmod p$$
and similarly for $q$.

answered 1 hour ago

Bernard

114k637106

add a commentÂ |Â

up vote
1
down vote

I suppose you mean $pq$ divides $, a^pq-a^p-a^q+a$, i.e.
$$ a^pq-a^p-a^q+aequiv 0pmodpq.$$

Hint:

By the Chinese remainder theorem, it amounts to proving it is congruent to $0$ $bmod p$ and $bmod q$.

As $p$ and $q$ are prime, remember Little Fermat can be formulated as
$$forall a,: a^pequiv apmod p$$
and similarly for $q$.

answered 1 hour ago

Bernard

114k637106

I suppose you mean $pq$ divides $, a^pq-a^p-a^q+a$, i.e.
$$ a^pq-a^p-a^q+aequiv 0pmodpq.$$

Hint:

By the Chinese remainder theorem, it amounts to proving it is congruent to $0$ $bmod p$ and $bmod q$.

As $p$ and $q$ are prime, remember Little Fermat can be formulated as
$$forall a,: a^pequiv apmod p$$
and similarly for $q$.

answered 1 hour ago

Bernard

114k637106

answered 1 hour ago

Bernard

114k637106

answered 1 hour ago

Bernard

114k637106

answered 1 hour ago

Bernard

114k637106

add a commentÂ |Â

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Search This Blog

Iyfjky