Vacated and remanded by published opinion. Judge THACKER wrote the majority opinion, in which Judge KING joined. Judge SHEDD wrote a dissenting opinion.
THACKER, Circuit Judge:
Appellant Fabian Montes-Flores (“Appellant”) challenges his sentence of 46 months imprisonment, imposed as a result [361]*361of his conviction pursuant to a violation of 8 U.S.C. § 1326 for illegal reentry into the United States after being previously removed. In this appeal, Appellant argues the district court erred by employing the modified categorical approach to determine that his prior conviction for assault and battery of a high and aggravated nature (“ABHAN”) under South Carolina law was a “crime of violence” for purposes of the 16-level enhancement authorized by the Sentencing Guidelines. See United States Sentencing Guideline (“U.S.S.G.”) § 2L1.2(b)(l)(A)(ii) (2012). Because we find the district court’s application of the modified categorical approach to ABHAN — an indivisible common law crime — was in error, we vacate Appellant’s sentence and remand for resentencing.
I.
A.
On June 12, 2010, Charleston, South Carolina police officers initiated a traffic stop on a vehicle in which Appellant was a passenger. The officers noticed an open container of alcohol and asked the driver and Appellant to exit the vehicle. As Appellant was exiting the vehicle, an officer observed a handgun sticking out from underneath a towel on Appellant’s seat. The handgun was a revolver, and it was loaded with six rounds of .357 ammunition. Police officers found three additional rounds of .357 ammunition in Appellant’s pocket. Appellant was charged with unlawful carrying of a firearm in violation of South Carolina law.
On June 17, 2010, an Immigration and Customs Enforcement (“ICE”) agent received Appellant’s fingerprints from the Charleston County Detention Center. An ICE Special Agent then determined Appellant had previously been deported in May 2008, following a 2006 conviction for ABHAN in South Carolina state court. The South Carolina ABHAN indictment to which Appellant pled guilty alleged:
That [Appellant] did in Charleston County on or about March 27, 2006 commit an assault and battery upon [the victim], constituting an unlawful act of violent injury to [the victim], to wit: [Appellant] assaulted the victim causing physical injury threatening her safety, accompanied by circumstances of aggravation including, but not limited to: use of his hands. This is in violation of the Common Law of the State of South Carolina.
J.A. 48.1
On November 8, 2011, a federal grand jury in the District of South Carolina returned a two-count indictment charging Appellant with illegal reentry after a prior removal for a conviction of an aggravated felony, in violation of 8 U.S.C. §§ 1326(a) and (b)(2),2 and with being an illegal alien in possession of a firearm and ammunition, in violation of 18 U.S.C. §§ 922(g)(5)(A), 924(a)(2), and 924(e). On June 7, 2012, Appellant entered a guilty plea to the illegal reentry charge, and the Government agreed to dismiss the remaining firearm and ammunition charge. During the plea proceeding, Appellant reserved the right to argue at sentencing that he was guilty [362]*362of illegal reentry after a felony conviction, as opposed to illegal reentry after an aggravated felony conviction.3
B.
Before sentencing, the United States Probation Office completed a Presentence Investigation Report (“PSR”)- The PSR calculated Appellant’s base offense level under U.S.S.G. § 2L1.2 (the “illegal reentry Guideline”) as eight, but it added a 16-level enhancement for Appellant’s prior ABHAN conviction, which the PSR classified as a “crime of violence” under U.S.S.G. § 2L1.2(b)(l)(A)(ii). After a three-level reduction for acceptance of responsibility, the PSR set Appellant’s total offense level at 21. The offense level, considered in combination with Appellant’s applicable criminal history category — calculated at III — provided for an advisory Guidelines range of 46 to 57 months.
Both before and during his sentencing hearing, Appellant argued that his prior conviction for ABHAN should not be considered a “crime of violence” under the illegal reentry Guideline. Citing our decision in United States v. Gomez, 690 F.3d 194, 200 (4th Cir.2012), Appellant urged the district court to employ the categorical approach in considering whether ABHAN is a crime of violence because “the South Carolina crime of ABHAN is a single, broad crime which may be committed in both violent and non-violent ways, both with and without force.” J.A. 43-44. In the alternative, Appellant argued ABHAN is not a crime of violence even under the modified categorical approach. The Government, however, asserted that ABHAN is a crime of violence under the modified categorical approach. Relying on several of our unpublished decisions, the Government maintained that employing the modified categorical approach was appropriate because “[t]he 4th Circuit has recently remanded a number of cases involving ABHAN convictions in order for the District Court to apply a modified categorical approach.” Id. at 51.
At the sentencing hearing held on September 18, 2012, the district court applied the modified categorical approach, noting that doing so seemed “to be consistent with the case law.” J.A. 61. After reviewing the indictment and sentencing sheet for Appellant’s ABHAN conviction,4 the district court concluded Appellant’s prior ABHAN conviction constituted a crime of violence under the modified categorical approach. In so concluding, the district court stated Appellant’s ABHAN conviction was “an offense in which the use, attempted use[,] or threatened use of physical force was involved.” Id. at 76. Accordingly, the district court held that a 16-level enhancement under the illegal [363]*363reentry Guideline was appropriate.5 See U.S.S.G. § 2L1.2 (b)(1)(A)(ii).
After considering the Sentencing Guidelines, as well as the factors set forth in 18 U.S.C. § 3553(a), the district court imposed a sentence of 46 months imprisonment, at the bottom of the advisory Guidelines range. In explaining its sentence, the district court noted, “there is something to be said that defendant continues to be engaged in conduct that is potentially very dangerous to people and violating the law.” J.A. 90. The court continued, “I think Mr. Montes-Flores is telling us he is a potential danger to the public. And you know, I have a concern about trying to get his attention not to try to return across the border.” Id. at 91. The district court concluded by explaining that it sought to deter Appellant by imposing a sentence “that would cause him to be disinclined to again violate the borders of the United States.” Id. at 95. The district court entered its judgment order on September 19, 2012, and Appellant timely noted this appeal. We have jurisdiction pursuant to 28 U.S.C. § 1291 and 18 U.S.C. § 3742(a).
II.
“Whether the district court erred in characterizing a defendant’s crime as a ‘crime of violence’ for sentence enhancement purposes is a question of law, which we review de novo.” United States v. Gomez, 690 F.3d 194, 197 (4th Cir.2012). “We rely on precedents evaluating whether an offense constitutes a ‘crime of violence’ under the Guidelines interchangeably with precedents evaluating whether an offense constitutes a ‘violent felony’ under the [Armed Career Criminal Act (“ACCA”)], because the two terms have been defined in a manner that is ‘substantively identical.’” United States v. King, 673 F.3d 274, 279 n. 3 (4th Cir.2012) (quoting United States v. Jamón, 596 F.3d 228, 231 n. * (4th Cir.2010)).6
III.
The applicable Sentencing Guideline for a conviction pursuant to 8 U.S.C. § 1326 is U.S.S.G. § 2L1.2. This illegal reentry Guideline designates a base offense level of eight and provides for various offense level enhancements depending on the specific characteristics of a particular defendant’s offense. See U.S.S.G. §§ 2L1.2(a), (b). At issue here is the 16-level enhancement that applies in cases where the defendant was removed from the United States after “a conviction for a felony that is ... a crime of violence.” Id. § 2L1.2 (b)(l)(A)(ii). “Crime of violence” is defined in the Application Notes as any [364]*364of the following crimes under federal, state, or local law:
[MJurder, manslaughter, kidnapping, aggravated assault, forcible sex offenses (including where consent to the conduct is not given or is not legally valid, such as where consent to the conduct is involuntary, incompetent, or coerced), statutory rape, sexual abuse of a minor, robbery, arson, extortion, extortionate extension of credit, burglary of a dwelling, or any other offense under federal, state, or local law that has as an element the use, attempted use, or threatened use of physical force against the person of another.
Id. § 2L1.2 cmt. n.l(B)(iii) (emphasis supplied).7
In assessing whether an offense constitutes a crime of violence under the Sentencing Guidelines, “two types of analyses are potentially applicable — known as the ‘categorical’ approach and the ‘modified categorical’ approach.” United States v. Harcum, 587 F.3d 219, 222 (4th Cir. 2009) (explaining the two potential approaches in the context of ACCA predicate offenses). Here, using the modified categorical approach, the district court concluded Appellant’s ABHAN conviction met the definition of a “crime of violence” because it was “an offense in which the use, attempted use[,J or threatened use of physical force was involved.” J.A. 76.
Categorical Approach
In determining whether a prior conviction triggers a sentence enhancement under the Sentencing Guidelines, “we approach the issue categorically, looking ‘only to the fact of conviction and the statutory definition of the prior offense.’ ” United States v. Cabrerar-Umanzor, 728 F.3d 347, 350 (4th Cir.2013) (quoting Taylor v. United States, 495 U.S. 575, 602, 110 S.Ct. 2143, 109 L.Ed.2d 607 (1990)). This categorical approach “focuses on the elements of the prior offense rather than the conduct underlying the conviction.” Id. (emphasis in original); United States v. Torres-Miguel, 701 F.3d 165, 167 (4th Cir. 2012); see also Begay v. United States, 553 U.S. 137, 141, 128 S.Ct. 1581, 170 L.Ed.2d 490 (2008) (“In determining whether [a] crime is a violent felony, we consider the offense generically, that is to say, we examine it in terms of how the law defines the offense and not in terms of how an individual offender might have committed it on a particular occasion.”). As we have recently explained, “[t]he point of the categorical inquiry is not to determine whether the defendant’s conduct could support a conviction for a crime of violence, but to determine whether the defendant was in fact convicted of a crime that qualifies as a crime of violence.” Cabrera-Umanzor, 728 F.3d at 350 (emphasis in original) (citing Descamps v. United States, — U.S. -, 133 S.Ct. 2276, 2288, 186 L.Ed.2d 438 (2013)).
Modified Categorical Approach
In a “narrow range of cases,” we may apply a modified categorical approach. Taylor, 495 U.S. at 602, 110 S.Ct. 2143. However, this approach is permitted only if the prior state conviction rests on a divisible statute — that is, a statute [365]*365that “contains divisible categories of proscribed conduct, at least one of which constitutes — by its elements — a violent felony.” United States v. Gomez, 690 F.3d 194, 199 (4th Cir.2012). In other words, we stray from use of the categorical approach only in cases involving “statutes that set out elements in the alternative and thus create multiple versions of the crime.” Cabrera-Umanzor, 728 F.3d at 350 (citing Descamps, 133 S.Ct. at 2284; Gomez, 690 F.3d at 199); see United States v. Hemingway, 734 F.3d 323, 327-29, No. 12-4362, 2013 WL 5833283, at *2 (4th Cir. Oct. 31, 2013) (explaining that the Supreme Court “contemplated that the modified categorical approach would be used only when the definition of the offense of conviction comprises multiple, alternative versions of the crime”) (internal quotation marks omitted). “General divisibility, however, is not enough; a statute is divisible for purposes of applying the modified' categorical approach only if at least one of the categories into which the statute may be divided constitutes, by its elements, a crime of violence.” Cabrera-Umanzor, 728 F.3d at 352 (emphasis in original).
In employing the modified categorical approach, a sentencing court is permitted to examine a finite class of extra-statutory materials “to determine which statutory phrase was the basis for the conviction.” Johnson v. United States, 559 U.S. 133, 144, 130 S.Ct. 1265, 176 L.Ed.2d 1 (2010). However, this examination is strictly limited to the following documents: “the terms of the charging document, the terms of a plea agreement or transcript of colloquy between judge and defendant in which the factual basis for the plea was confirmed by the defendant, or to some comparable judicial record of this information.” Shepard v. United States, 544 U.S. 13, 26, 125 S.Ct. 1254, 161 L.Ed.2d 205 (2005). In reviewing those documents, the district court’s sole purpose is to “deter-min[e] which statutory phrase (contained within a statutory provision that covers several different generic crimes) covered a prior conviction.” Nijhawan v. Holder, 557 U.S. 29, 41, 129 S.Ct. 2294, 174 L.Ed.2d 22 (2009); see also Gomez, 690 F.3d at 198 (explaining that the examination of Shepard-approved documents “is for the sole purpose of determining which part of the statute the defendant violated”).
As the Supreme Court has reiterated, “the modified categorical approach serves a limited function: It helps effectuate the categorical analysis when a divisible statute, listing potential offense elements in the alternative, renders opaque which element played a part in the defendant’s conviction.” Descamps, 133 S.Ct. at 2283.
Accordingly, the modified categorical approach is applicable only “when a defendant was convicted of violating a divisible statute,” and then, “only to determine which alternative element ... formed the basis of the defendant’s conviction.” Descamps, 133 S.Ct. at 2285, 2293; see also Gomez, 690 F.3d at 200 (“Thus, if the statute is divisible, with some categories constituting a crime of violence and some not constituting a crime of violence, then it is appropriate for the district court to employ the modified categorical approach ... to ascertain whether the defendant violated a crime-of-violence category of the statute.”).
C.
Assault and Battery of a High and Aggravated Nature
With this framework in mind, we must determine what approach a sentencing court must employ when deciding if a prior ABHAN conviction was for a crime of [366]*366violence under the Sentencing Guidelines. Resolution of this issue turns on whether the Descamps divisibility analysis applies to common law crimes and, if so, whether ABHAN is divisible.
We recently addressed both of these issues in a related context — namely, whether ABHAN constitutes a predicate “violent felony” under the ACCA’s residual clause. See United States v. Hemingway, 734 F.3d 323, 330, No. 12-4362, 2013 WL 5833283, at *4 (4th Cir. Oct. 31, 2013). In November 2011, Hemingway pled guilty to illegal possession of a firearm and ammunition after having previously been convicted of a felony, in violation of 18 U.S.C. § 922(g)(1). Id. 329-30, 2013 WL 5833283, at *3. Before sentencing, Hemingway objected to his PSR’s recommendation to enhance his sentence under the ACCA, arguing “that two of the four crimes identified in the PSR — ABHAN and its lesser included offense of assault of a high and aggravated nature (“AHAN”) — are not predicate offenses under the ACCA because they do not constitute ACCA violent felonies.” Id. The district court disagreed, however, and ruled Hemingway’s ABHAN offense was for a violent felony under the ACCA’s residual clause. Id. 330-31, 2013 WL 5833283, at *4.8 The district court employed the categorical approach in reaching this conclusion.9
On appeal, Hemingway argued that ABHAN is not categorically an ACCA violent felony and, contrary to the Government’s position on appeal, that the modified categorical approach was inapplicable to this determination. Hemingway, 734 F.3d at 330-31, 2013 WL 5833283, at *4. Relying on the Supreme Court’s recent decision in Descamps, we agreed. Id. at 331-32, 338, 2013 WL 5833283, at *5, *11. As an initial matter, we squarely held, “the Descamps divisibility analysis is applicable to the question of whether a common law offense constitutes an ACCA predicate crime.” Id. at 333, 2013 WL 5833283, at *6. We then reviewed the common law offense of ABHAN, as defined by the South Carolina courts, and determined that because it consists of two indivisible elements, “the modified categorical approach has no role to play.” Id. at 334, 2013 WL 5833283, at *7 (internal quotation marks omitted). Having decided the categorical approach is the proper method of analysis, we assessed whether ABHAN qualifies as an ACCA violent felony under the residual clause and held that it does not. Id. at 336-38, 2013 WL 5833283, at *10.
Although Hemingway involved the determination of whether ABHAN was a “violent felony” under the ACCA’s residual clause, its analysis of Descamps is equally applicable in determining whether ABHAN is a “crime of violence” in the Sentencing Guidelines context. See Cabrera-Umanzor, 728 F.3d at 350, 352 (applying the Descamps divisibility analysis to [367]*367the “crime of violence” enhancement under the illegal reentry Guideline).
1.
Common Law Crimes
We reiterate that, by its terms, the Des-camps holding, which dealt with an indivisible California burglary statute, does not expressly apply to common law crimes. See Hemingway, 734 F.3d at 329-30, 2013 WL 5833283, at *3 (explaining that Des-camps “left open the issue of whether the divisibility analysis applies to a common law crime”). Similarly, in Gomez, we did not decide whether the divisibility analysis applies in the common law context. United States v. Gomez, 690 F.3d 194, 202 (“Here, however, we are concerned with the divisions within a statute, not a common law crime.”). In Hemingway, however, we answered the question directly, holding the “divisibility analysis is applicable to the question of whether a common law offense constitutes an ACCA predicate crime.” 734 F.3d at 333, 2013 WL 5833283, at *6. In so holding, we explained that nothing in the Supreme Court’s decision in Descamps “suggests that a divisibility analysis does not apply with equal force to a common law offense.” Id. at 332, 2013 WL 5833283, at *6. Therefore, because the divisibility analysis applies generally to sentence enhancements for crimes of violence, Hemingway’s conclusion that divisibility applies to common law offenses in the ACCA context is equally applicable here.
We agree with our sister circuits that, when a “state crime is defined by specific and identifiable common law elements, rather than by a specific statute, the common law definition of a crime serves as a functional equivalent of a statutory definition.” United States v. Walker, 595 F.3d 441, 444 (2d Cir.2010) (internal quotation marks omitted). We too have treated common law crimes and statutory crimes as functionally equivalent for sentence enhancement purposes, and Hemingway is clear that “the modified categorical approach has ‘no role to play’ where the previous crime was an indivisible common law offense.” Hemingway, 734 F.3d at 333, 2013 WL 5833283, at *6 (quoting Descamps, 133 S.Ct. at 2285).
2.
Divisibility
Having concluded that the divisibility analysis applies to common law offenses for purposes of enhancements under the Sentencing Guidelines, we must next decide whether South Carolina’s common law crime of ABHAN is divisible such that the modified categorical approach applies.10 A statute is “divisible” when it is comprised of “multiple, alternative versions of the crime.” Descamps, 133 S.Ct. at 2284. Stated differently, statutes are divisible if they “set out elements in the alternative and thus create multiple ver[368]*368sions of the crime.” Cabrera-Umanzor, 728 F.3d at 350. Under this standard, ABHAN is not divisible.
Until it was codified in 2010, ABHAN was a common law crime in South Carolina defined as “the unlawful act of violent injury to another accompanied by circumstances of aggravation.” State v. Green, 397 S.C. 268, 724 S.E.2d 664, 674 (2012) (internal quotation marks omitted).11 The “violent injury” element does not require actual bodily harm to another. Indeed, common law ABHAN included such offenses as “a stranger on the street embracing] a young lady, or a large man improperly fondl[ing] a child.” State v. DeBerry, 250 S.C. 314, 157 S.E.2d 637, 640 (1967). Qualifying circumstances of aggravation include, but are not limited to:
the use of a deadly weapon, the intent to commit a felony, infliction of serious bodily injury, great disparity in the ages or physical conditions of the parties, a difference in gender, the purposeful infliction of shame and disgrace, taking indecent liberties or familiarities with a female, and resistance to lawful authority-
State v. Fennell, 340 S.C. 266, 531 S.E.2d 512, 516-17 (2000) (collecting cases).
South Carolina courts have specifically referred to the “circumstances of aggravation” as a separate element. See State v. Easler, 327 S.C. 121, 489 S.E.2d 617, 624 (1997) (applying the double jeopardy analysis pursuant to Blockburger v. United States, 284 U.S. 299, 52 S.Ct. 180, 76 L.Ed. 306 (1932), and explaining that “[a]s to the element of ABHAN which is not contained in felony DUI, ABHAN requires proof of ‘circumstances of aggravation,’ something which is not required for felony DUI”); Knox v. State, 340 S.C. 81, 530 S.E.2d 887, 889 (2000), overruled on other grounds by State v. Gentry, 363 S.C. 93, 610 S.E.2d 494, 502 (2005) (determining whether ABHAN is a lesser included offense of second degree lynching and explaining that “ ‘[c]ircumstances of aggravation’ is an element of ABHAN not included in second degree lynching”); State v. Primus, 349 S.C. 576, 581, 564 S.E.2d 103 (2002), overruled on other grounds by Gentry, 610 S.E.2d at 501 (“‘Circumstances of aggravation’ is an element of ABHAN.”). To be sure, the myriad “circumstances of aggravation” “simply identify the specific ways the second element of ABHAN can be satisfied.” Hemingway, 734 F.3d at 334, 2013 WL 5833283, at *7. They are not themselves elements or sub-elements of ABHAN. Id.
After explaining that proof of “circumstances of aggravation” is required for an ABHAN conviction, South Carolina courts identify various aggravating circumstances that can satisfy this element. See, e.g., Fennell, 531 S.E.2d at 516-17. As we observed in Hemingway, this enumeration by the South Carolina courts is merely a non-exhaustive list of examples that will sustain an ABHAN conviction; it is not a list of “ ‘potential offense elements in the alternative,’ so as to warrant our application of the modified categorical approach.” Hemingway, 734 F.3d at 333, 2013 WL 5833283, at *7 (quoting Descamps, 133 S.Ct. at 2283).
Consistent with our analysis in Hemingway, it is clear that ABHAN is comprised of two indivisible elements: (1) an unlawful act of violent injury to another; and (2) circumstances of aggravation. See Hemingway, 734 F.3d at 333-34, 2013 WL 5833283, at *7. For that reason, employing the modified categorical approach to determine whether Appellant’s ABHAN convic[369]*369tion was for a “crime of violence” was improper in this case.
D.
Application of the Categorical Approach to ABHAN
Because the modified categorical approach is inapplicable to ABHAN, we must apply the categorical approach, which looks only to the fact of conviction and the definition of the prior offense to determine whether the conduct criminalized, “including the most innocent, conduct, qualifies as a ‘crime of violence.’ ” See Torres-Miguel, 701 F.3d at 167.12 The relevant portion of the illegal reentry Guideline defines “crime of violence” as an “offense under federal, state, or local law that has as an element the use, attempted use, or threatened use of physical force against the person of another.” U.S.S.G. § 2L1.2 cmt. n.l(B)(iii) (emphasis supplied). In Johnson v. United States, the Supreme Court explained, “the phrase ‘physical force’ means violent force — that is, force capable of causing physical pain or injury to another person.” 559 U.S. 133, 140, 130 S.Ct. 1265, 176 L.Ed.2d 1 (2010) (emphasis in original). As explained in the divisibility analysis above, although ABHAN is defined as “the unlawful act of violent injury to another accompanied by circumstances of aggravation,” Green, 724 S.E.2d at 674, a conviction for ABHAN does not require actual bodily harm to another, see DeBerry, 157 S.E.2d at 640. See also State v. Patterson, 337 S.C. 215, 522 S.E.2d 845, 853 (Ct.App. 1999) (“[B]odily harm is not even a prerequisite to an ABHAN conviction.”). Likewise, force against the victim is not required to sustain an ABHAN conviction. State v. Green, 327 S.C. 581, 491 S.E.2d 263, 265 (Ct.App.1997). Because ABHAN can be committed with or without force— and even when force is involved, ABHAN can be committed in a violent or nonviolent manner — a conviction for ABHAN is not categorically for a crime of violence.13 Accordingly, Appellant’s sentence must be vacated and this case remanded for resen-tencing.
IV.
In the alternative, the Government argues, even if the district court incorrectly calculated Appellant’s Senténcing Guidelines range by erroneously applying the 16-level enhancement, any error was harmless because the district court’s imposition of the enhancement did not affect his ultimate sentence. The Government argues that “[t]here can be little doubt that Appellant would have received the same sentence,” Appellee’s Br. 17, because the district court’s analysis “shows that it’s [sic] determination of Appellant’s sentence was based on a thorough and careful analysis of the” 18 U.S.C. § 3553(a) factors, id. at 16. Although we agree that the district court considered the various factors in [370]*370§ 3553(a)—a step that is required at every sentencing, see United States v. Johnson, 445 F.3d 339, 345 (4th Cir.2006)—we are not persuaded that it would have imposed the same sentence absent the 16-level enhancement.
As we have observed, “because a correct calculation of the advisory Guidelines range is the crucial ‘starting point’ for sentencing, an error at that step ‘infects all that follows at the sentencing proceeding, including the ultimate sentence chosen by the district court.’ ” United States v. Lewis, 606 F.3d 193, 201 (4th Cir.2010) (quoting United States v. Diaz-Ibarra, 522 F.3d 343, 347 (4th Cir.2008)). Nevertheless, procedural errors at sentencing are subject to harmlessness review. See United States v. Lynn, 592 F.3d 572, 576 (4th Cir.2010).
In order for us to conclude that a sentencing error was harmless, we must make two separate determinations. First, we must “know[ ] that the district court would have reached the same result even if it had decided the [Guidelines issue the other way.” United States v. Savillon-Matute, 636 F.3d 119, 123 (4th Cir.2011) (internal quotation marks omitted). Once we are “certain” that the result at sentencing would have been the same, we must next “determin[e] that the sentence would be reasonable even if the [Guidelines issue had been decided in the defendant’s favor.” United States v. Gomez, 690 F.3d 194, 203 (4th Cir.2012) (alteration in original) (internal quotation marks omitted).
Of course, there is no requirement that a district court “specifically state that it would give the same sentence absent the [enhancement].” Savillon-Matute, 636 F.3d at 124. Again, however, to conclude that an error at sentencing was harmless, the record from the sentencing hearing must provide the reviewing court with “knowledge that the district court would have reached the same result even if it had decided the [Guidelines issue the other way.” Id. at 123 (emphasis supplied) (internal quotation marks omitted). For us to possess the required “knowledge,” something more than a review by the district court of the § 3553(a) factors is needed, particularly since an assessment of those factors is required at every sentencing. See Gomez, 690 F.3d at 203 (“Although the district court did a commendable job in considering the 18 U.S.C. 3553(a) factors in determining the sentence that it would impose, we are unable to state with any certainty that it would have imposed the same sentence had the sixteen-level enhancement not been in play.”).
During Appellant’s sentencing hearing, the district court discussed a number of the § 3553(a) factors, focusing primarily on deterrence. See 18 U.S.C. § 3553(a)(2)(B). For instance, the court noted, “there is something to be said that defendant continues to be engaged in conduct that is potentially very dangerous to people and violating the law.” J.A. 90. The court also expressed its “concern about trying to get his attention not to try to return across the border.” Id. at 91. The court then explained that it sought to deter Appellant by imposing a sentence “that would cause him to be disinclined to again violate the borders of the United States.” Id. at 95. Although the record is clear that the court carefully considered the § 3553(a) factors in determining the sentence it would impose, the record does not support the conclusion that Appellant would have received the same sentence if the court had not applied the 16-level enhancement.
With the 16-level enhancement, Appellant’s Sentencing Guidelines range was 46 to 57 months imprisonment. However, without the “crime of violence” enhance[371]*371ment, his Guidelines range would have been either 18 to 24 months (applying the “aggravated felony” enhancement)14 or 10 to 16 months (applying the “felony” enhancement).15 The district court’s sentence of 46 months was thus at the bottom of what it incorrectly considered to be the Guidelines range. Its discussion of the § 3553(a) factors was in the context of the erroneous Guidelines calculation, and there is nothing in the record to suggest the court would have varied upward from a Guidelines range of 10 to 16 months or 18 to 24 months to arrive at a 46 month sentence.
Although Savillonr-Matute may be instructive, it is readily distinguishable. There, the district court adopted the PSR, including the advisory Guidelines range of 12 to 18 months, and then imposed a sentence of 36 months, well above the advisory Guidelines range. Savillonr-Matute, 636 F.3d at 121, 122. Thus, the district court’s imposition of a substantially above-Guidelines sentence, coupled with an explicit explanation for the upward variance, readily supported an inference that the court would have imposed the same sentence had the Guidelines calculation been different. See id. at 122 (summarizing court’s justification under the' § 3553(a) factors for its upward variance). Where, as here, the district court imposes a within-Guidelines sentence, we cannot assume (much less know) that the court, faced with a much lower advisory range, would have varied upward by at least 22 months. Although we review a sentence for abuse of discretion — whether within or outside the Guidelines range — the Supreme Court has directed that “when applying a departure provision or varying from the Guidelines range, the district court must give ‘serious consideration to the extent’ of the departure or variance, and ‘must adequately explain the chosen sentence to allow for meaningful appellate review and to promote the perception of fair sentencing.’ ” United States v. Diosdado-Star, 630 F.3d 359, 365 (4th Cir.2011) (quoting Gall v. United States, 552 U.S. 38, 46, 128 S.Ct. 586,169 L.Ed.2d 445 (2007)).
Because the district court did not vary in this case, it also did not offer any justification for an above-Guidelines sentence. The standard for harmlessness — knowledge of an identical outcome — is a high bar, and in this situation we are not so omniscient as to possess the requisite knowledge. In such circumstances, we cannot conclude that the district court’s error was harmless.
V.
Pursuant to the foregoing, we vacate Appellant’s sentence and remand for re-sentencing.
VACATED AND REMANDED.